{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Flips to Make the Binary String Alternating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minFlips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使二进制字符串字符交替的最少反转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串 <code>s</code> 。你可以按任意顺序执行以下两种操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>类型 1 ：删除</strong> 字符串 <code>s</code> 的第一个字符并将它 <strong>添加</strong> 到字符串结尾。</li>\n",
    "\t<li><strong>类型 2 ：选择 </strong>字符串 <code>s</code> 中任意一个字符并将该字符 <strong>反转 </strong>，也就是如果值为 <code>'0'</code> ，则反转得到 <code>'1'</code> ，反之亦然。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回使 <code>s</code> 变成 <strong>交替</strong> 字符串的前提下， <strong>类型 2 </strong>的 <strong>最少</strong> 操作次数 。</p>\n",
    "\n",
    "<p>我们称一个字符串是 <strong>交替</strong> 的，需要满足任意相邻字符都不同。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，字符串 <code>\"010\"</code> 和 <code>\"1010\"</code> 都是交替的，但是字符串 <code>\"0100\"</code> 不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"111000\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>执行第一种操作两次，得到 s = \"100011\" 。\n",
    "然后对第三个和第六个字符执行第二种操作，得到 s = \"10<strong>1</strong>01<strong>0</strong>\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"010\"\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>字符串已经是交替的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"1110\"\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>对第二个字符执行第二种操作，得到 s = \"1<strong>0</strong>10\" 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 要么是 <code>'0'</code> ，要么是 <code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-flips-to-make-the-binary-string-alternating](https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-flips-to-make-the-binary-string-alternating](https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"111000\"', '\"010\"', '\"1110\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        temp = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    temp |= (1 << i*n+j)\n",
    "        visit = set([temp])\n",
    "        q = deque([(temp, 0)])\n",
    "        while q:\n",
    "            now, dist = q.popleft()\n",
    "            if now == 0:\n",
    "                return dist\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    nex = now\n",
    "                    for a, b in [(i, j), (i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                        if 0 <= a < m and 0 <= b < n:\n",
    "                            if now & (1 << a*n+b):\n",
    "                                nex &= ~(1 << a*n+b)\n",
    "                            else:\n",
    "                                nex |= (1 << a*n+b)\n",
    "                    if nex not in visit:\n",
    "                        q.append((nex, dist+1))\n",
    "                        visit.add(nex)           \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        # 矩阵转二进制数\n",
    "        def encode(mat):\n",
    "            x = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    x = x*2 + mat[i][j]\n",
    "            return x\n",
    "        # 二进制数转矩阵\n",
    "        def decode(x):\n",
    "            mat = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    mat[i][j] = x&1\n",
    "                    x >>= 1\n",
    "            return mat\n",
    "        def convert(state,i,j):\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "                i0, j0 = i + di, j + dj\n",
    "                if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                    state[i0][j0] ^= 1\n",
    "        # 广度优先搜索\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        seen = {initial}\n",
    "        q = [initial]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                state = decode(x)\n",
    "                # 枚举翻转的位置\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        # 翻转一次\n",
    "                        convert(state,i,j)\n",
    "                        y = encode(state)\n",
    "                        if y == 0:\n",
    "                            return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        # 翻转回去\n",
    "                        convert(state,i,j)\n",
    "            step += 1        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        vv = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vv = (vv << 1) + mat[i][j]\n",
    "        if vv == 0: return 0\n",
    "        ans = [-1] * (1 << m * n)\n",
    "        ans[0] = 0\n",
    "        q = [0]\n",
    "        d = 0\n",
    "        while q:\n",
    "            t = []\n",
    "            for v in q:\n",
    "                for s in range(m * n):\n",
    "                    i, j = divmod(s, n)\n",
    "                    nv = v ^ (1 << s)\n",
    "                    for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if ni < 0 or ni >= m or nj < 0 or nj >= n: continue\n",
    "                        nv ^= 1 << (ni * n + nj)\n",
    "                    if ans[nv] == -1:\n",
    "                        ans[nv] = d + 1\n",
    "                        if vv == nv: return d + 1\n",
    "                        t.append(nv)\n",
    "            d += 1\n",
    "            q = t\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = 1e9\n",
    "        for binary in range(0, 1 << n):\n",
    "            mat_copy = [line[:] for line in mat]\n",
    "            flip_cnt = 0\n",
    "            for j in range(n):\n",
    "                if binary & (1 << j):\n",
    "                    flip_cnt += 1\n",
    "                    self.convert(mat_copy, m, n, 0, j)\n",
    "\n",
    "            for i in range(1, m):\n",
    "                for j in range(n):\n",
    "                    if mat_copy[i - 1][j] == 1:\n",
    "                        flip_cnt += 1\n",
    "                        self.convert(mat_copy, m, n, i, j)\n",
    "\n",
    "            if all(mat_copy[m - 1][j] == 0 for j in range(n)):\n",
    "                ans = min(ans, flip_cnt)\n",
    "        return ans if ans != 10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        visit = set()\n",
    "        lst = []\n",
    "        for ma in mat:\n",
    "            lst.extend(ma)\n",
    "        visit.add(tuple(lst))\n",
    "        stack = deque([[lst, 0]])\n",
    "        while stack:\n",
    "            lst, d = stack.popleft()\n",
    "            if all(x==0 for x in lst):\n",
    "                return d\n",
    "            for i in range(m*n):\n",
    "                x, y = i//n, i%n\n",
    "                tmp = lst[:]\n",
    "                tmp[i] = 1-tmp[i]\n",
    "                for a, b in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:\n",
    "                    if 0<=a<m and 0<=b<n:\n",
    "                        tmp[a*n+b] = 1-tmp[a*n+b]\n",
    "                if tuple(tmp) not in visit:\n",
    "                    visit.add(tuple(tmp))\n",
    "                    stack.append([tmp, d+1])\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        \n",
    "        def flip(x, y):\n",
    "            directions = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    mat[nx][ny] = 1 - mat[nx][ny]\n",
    "        \n",
    "        def check_zero_matrix(mat):\n",
    "            for row in mat:\n",
    "                for num in row:\n",
    "                    if num != 0:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if x == m:\n",
    "                if check_zero_matrix(mat):\n",
    "                    self.min_flips = min(self.min_flips, self.flip_count)\n",
    "                return\n",
    "            if y == n:\n",
    "                dfs(x + 1, 0)\n",
    "                return\n",
    "            \n",
    "            # 不反转当前格子\n",
    "            dfs(x, y + 1)\n",
    "            \n",
    "            # 反转当前格子\n",
    "            flip(x, y)\n",
    "            self.flip_count += 1\n",
    "            dfs(x, y + 1)\n",
    "            flip(x, y)  # 恢复原始状态\n",
    "            self.flip_count -= 1\n",
    "        \n",
    "        self.min_flips = float('inf')\n",
    "        self.flip_count = 0\n",
    "        dfs(0, 0)\n",
    "        \n",
    "        return self.min_flips if self.min_flips != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        def stack(i, j):#以i，j为中心反转\n",
    "            for x, y in [[i, j], [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    mat[x][y] = 0 if mat[x][y] == 1 else 1\n",
    "            \n",
    "        def dfs(state):#状态位\n",
    "            if state == m * n:#如果所有点遍历完了\n",
    "                return 0 if sum(sum(i) for i in mat) == 0 else float(\"inf\")#根据是否有1来决定返回0或者inf\n",
    "            x, y = state // n, state % n#状态位转横纵坐标\n",
    "            res = dfs(state + 1)#不反转的结果\n",
    "            stack(x, y)#反转\n",
    "            res = min(res, 1 + dfs(state + 1))#找到和反转后的最小值\n",
    "            stack(x, y)#再次反转回溯\n",
    "            return res\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = dfs(0)\n",
    "        return res if res < float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        mask = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    mask |= 1 << (i * n + j)\n",
    "\n",
    "        q = deque([(mask, 0)])\n",
    "        vis = {mask, }\n",
    "        while q:\n",
    "            cur, step = q.popleft()\n",
    "            if cur == 0:\n",
    "                return step\n",
    "            for i in range(m * n):\n",
    "                r, c = divmod(i, n)  # 获取i的行，列\n",
    "                nxt = cur\n",
    "                for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                    if 0 <= nr < m and 0 <= nc < n:\n",
    "                        nxt ^= 1 << (nr * n + nc)  # 翻转i的四边\n",
    "                nxt ^= 1 << (r * n + c)  # 翻转i\n",
    "                if nxt not in vis:\n",
    "                    vis.add(nxt)\n",
    "                    q.append((nxt, step + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        # 矩阵转二进制数\n",
    "        def encode(mat):\n",
    "            x = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    x = x*2 + mat[i][j]\n",
    "            return x\n",
    "        # 二进制数转矩阵\n",
    "        def decode(x):\n",
    "            mat = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    mat[i][j] = x&1\n",
    "                    x >>= 1\n",
    "            return mat\n",
    "        def convert(state,i,j):\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "                i0, j0 = i + di, j + dj\n",
    "                if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                    state[i0][j0] ^= 1\n",
    "            return state\n",
    "        # 广度优先搜索\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        seen = {initial}\n",
    "        q = [initial]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                state = decode(x)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        state = convert(state,i,j)\n",
    "                        y = encode(state)\n",
    "                        if y == 0:\n",
    "                            return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        state = convert(state,i,j)\n",
    "            step += 1        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        q=[(mat,0)]\n",
    "        while (len(q)!=0):\n",
    "            q0=q.pop(0)\n",
    "            # print(q0,q)\n",
    "            s.add(self.flat(q0[0]))\n",
    "            if self.test(q0[0]):\n",
    "                return q0[1]\n",
    "            # print(q0[0])\n",
    "            m,n=len(q0[0]),len(q0[0][0])\n",
    "            # print(self.flat(q0[0]))\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # print(i,j)\n",
    "                    tempmat=copy.deepcopy(q0[0])\n",
    "                    # print(tempmat)\n",
    "                    tempmat[i][j]=1-tempmat[i][j]\n",
    "                    if i-1>=0:\n",
    "                        tempmat[i-1][j]=1-tempmat[i-1][j]\n",
    "                    if i+1<m:\n",
    "                        tempmat[i+1][j]=1-tempmat[i+1][j]\n",
    "                    if j-1>=0:\n",
    "                        tempmat[i][j-1]=1-tempmat[i][j-1]\n",
    "                    if j+1<n:\n",
    "                        tempmat[i][j+1]=1-tempmat[i][j+1]\n",
    "                    # print(tempmat)\n",
    "                    if self.flat(tempmat) not in s:\n",
    "                        q.append((tempmat, q0[1]+1))\n",
    "                        s.add(self.flat(tempmat))\n",
    "        return -1\n",
    "\n",
    "    def test(self, mat):\n",
    "        res=True\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]!=0:\n",
    "                    res=False\n",
    "        return res\n",
    "\n",
    "    def flat(self, mat):\n",
    "        x=0\n",
    "        res=0\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                res+= pow(10,x)*mat[i][j]\n",
    "                x+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, mat, m, n):\n",
    "        x = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = x * 2 + mat[i][j]\n",
    "        return x\n",
    "    \n",
    "    def decode(self, x, m, n):\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                mat[i][j] = x & 1\n",
    "                x >>= 1\n",
    "        return mat\n",
    "    \n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]\n",
    "        for di, dj in dirs:\n",
    "            ni, nj = i + di, j + dj\n",
    "            if 0 <= ni <= m-1 and 0 <= nj <=n-1:\n",
    "                mat[ni][nj] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        x_start = self.encode(mat, m, n)\n",
    "        step = 0\n",
    "        if x_start == 0:\n",
    "            return step\n",
    "\n",
    "        q = deque()\n",
    "        q.append(x_start)\n",
    "        \n",
    "        vis = {x_start}\n",
    "        \n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                # 列表中存的是10进制\n",
    "                cur_x = q.popleft()\n",
    "                # 从当前状态中进行枚举\n",
    "                status = self.decode(cur_x, m, n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.convert(status, m, n, i, j)\n",
    "                        new_x = self.encode(status, m, n)\n",
    "                        if new_x == 0:\n",
    "                            return step\n",
    "                        if not new_x in vis:\n",
    "                            q.append(new_x)\n",
    "                            vis.add(new_x)\n",
    "                        # 需要把状态再恢复回去\n",
    "                        self.convert(status, m, n, i, j)\n",
    "        return -1\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        def dfs(num: int, i: int, j: int) -> int:\n",
    "            if i >= self.m or j >= self.n:\n",
    "                return inf if num else 0\n",
    "            x = i + 1 if j == self.n - 1 else i\n",
    "            y = 0 if j == self.n - 1 else j + 1\n",
    "            return min(dfs(self.convert(num, i, j), x, y) + 1, dfs(num, x, y))\n",
    "\n",
    "        ans = dfs(self.enconde(mat), 0, 0)\n",
    "        return -1 if ans == inf else ans\n",
    "            \n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 10**9\n",
    "\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def dfs(self, mat, m, n, pos, flip_cnt):\n",
    "        if pos == m * n:\n",
    "            if all(mat[i][j] == 0 for i in range(m) for j in range(n)):\n",
    "                self.ans = min(self.ans, flip_cnt)\n",
    "            return\n",
    "\n",
    "        x, y = pos // n, pos % n\n",
    "        # not flip\n",
    "        self.dfs(mat, m, n, pos + 1, flip_cnt)\n",
    "        # flip\n",
    "        self.convert(mat, m, n, x, y)\n",
    "        self.dfs(mat, m, n, pos + 1, flip_cnt + 1)\n",
    "        self.convert(mat, m, n, x, y)\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.dfs(mat, m, n, 0, 0)\n",
    "        return self.ans if self.ans != 10**9 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = 1e9\n",
    "        for binary in range(0, 1 << n):\n",
    "            mat_copy = [line[:] for line in mat]\n",
    "            flip_cnt = 0\n",
    "            for j in range(n):\n",
    "                if binary & (1 << j):\n",
    "                    flip_cnt += 1\n",
    "                    self.convert(mat_copy, m, n, 0, j)\n",
    "\n",
    "            for i in range(1, m):\n",
    "                for j in range(n):\n",
    "                    if mat_copy[i - 1][j] == 1:\n",
    "                        flip_cnt += 1\n",
    "                        self.convert(mat_copy, m, n, i, j)\n",
    "\n",
    "            if all(mat_copy[m - 1][j] == 0 for j in range(n)):\n",
    "                ans = min(ans, flip_cnt)\n",
    "        return ans if ans != 10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        def encode(mat):\n",
    "            res = 0\n",
    "            # 矩阵变二进制数\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    res = res*2+mat[i][j]\n",
    "            return res\n",
    "        def otcode(x):\n",
    "            # 二进制数变成矩阵\n",
    "            res = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    res[i][j] = x & 1\n",
    "                    x >>= 1\n",
    "            return res\n",
    "        # def exchange(mat,i,j):\n",
    "        #     for x,y in (i,j),(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "        #         if 0 <= x < m and 0 <= y < n:\n",
    "        #             mat[i][j] ^= 1\n",
    "        def exchange(state,i,j):\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "                i0, j0 = i + di, j + dj\n",
    "                if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                    state[i0][j0] ^= 1\n",
    "        # BFS\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        q = [initial]\n",
    "        seen = {initial}\n",
    "        \n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                # 二进制数转为矩阵\n",
    "                state = otcode(x)\n",
    "                # 枚举翻转的位置\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        exchange(state,i,j)\n",
    "                        # 翻转完毕转为二进制数\n",
    "                        y = encode(state)\n",
    "                        if y == 0:return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        # 翻转回去\n",
    "                        exchange(state,i,j)\n",
    "                        \n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        def dfs(num: int, i: int, j: int) -> int:\n",
    "            if i >= self.m or j >= self.n:\n",
    "                return inf if num else 0\n",
    "            x = i + 1 if j == self.n - 1 else i\n",
    "            y = 0 if j == self.n - 1 else j + 1\n",
    "            if i != 0 and num & (1 << ((i - 1) * self.n + j)):\n",
    "                return dfs(self.convert(num, i, j), x, y) + 1\n",
    "            if i != 0 and num & (1 << ((i - 1) * self.n + j)) == 0:\n",
    "                return dfs(num, x, y)\n",
    "            return min(dfs(self.convert(num, i, j), x, y) + 1, dfs(num, x, y))\n",
    "\n",
    "        ans = dfs(self.enconde(mat), 0, 0)\n",
    "        return -1 if ans == inf else ans\n",
    "            \n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        def stack(i, j):#以i，j为中心反转\n",
    "            for x, y in [[i, j], [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    mat[x][y] = 0 if mat[x][y] == 1 else 1\n",
    "            \n",
    "        def dfs(state):#状态位\n",
    "            if state == m * n:#如果所有点遍历完了\n",
    "                return 0 if sum(sum(i) for i in mat) == 0 else float(\"inf\")#根据是否有1来决定返回0或者inf\n",
    "            x, y = state // n, state % n#状态位转横纵坐标\n",
    "            res = dfs(state + 1)#不反转的结果\n",
    "            stack(x, y)#反转\n",
    "            res = min(res, 1 + dfs(state + 1))#找到和反转后的最小值\n",
    "            stack(x, y)#再次反转回溯\n",
    "            return res\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = dfs(0)\n",
    "        return res if res < float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        def jd(s):\n",
    "            s = s.rjust(m*n, \"0\")\n",
    "            for x in range(m):\n",
    "                for y in range(n):\n",
    "                    v = mat[x][y]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and s[nx*n+ny] == \"1\": v = 1 - v\n",
    "                    if v: return False\n",
    "            return True\n",
    "        m, n, POS, res = len(mat), len(mat[0]), ((0,0), (0, 1), (1, 0), (0, -1), (-1, 0)), 10\n",
    "        for k in range(1<<m*n):\n",
    "            bk = bin(k)[2:]\n",
    "            if res > bk.count(\"1\"):\n",
    "                if jd(bk): res = bk.count(\"1\")\n",
    "        return res if res < 10 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        dq = deque([self.enconde(mat)])\n",
    "        v = set([self.enconde(mat)])\n",
    "        steps = 0\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            while size:\n",
    "                o = dq.popleft()\n",
    "                if o == 0:\n",
    "                    return steps\n",
    "                for i in range(self.m):\n",
    "                    for j in range(self.n):\n",
    "                        p = self.convert(o, i, j)\n",
    "                        if p in v:\n",
    "                            continue\n",
    "                        dq.append(p)\n",
    "                        v.add(p)\n",
    "                size -= 1\n",
    "            steps += 1\n",
    "        return -1\n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def decode(self, num: int) -> List[List[int]]:\n",
    "        mat = [[0] * self.n for _ in range(self.m)]\n",
    "        for x in range(num.bit_length()):\n",
    "            if num & (1 << x):\n",
    "                i, j = divmod(x, self.n)\n",
    "                mat[i][j] = 1\n",
    "        return mat\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        target = \"0\" * (m*n)\n",
    "\n",
    "        #print(target)\n",
    "\n",
    "        def encode(mat):\n",
    "            res = ''\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    res += str(mat[i][j])\n",
    "            return res\n",
    "        \n",
    "        def decode(s):\n",
    "            res = [[0] * n for _ in range(m)]\n",
    "            for i, si in enumerate(s):\n",
    "                idx, idy = divmod(i, n)\n",
    "                res[idx][idy] = int(si)\n",
    "            return res\n",
    "        \n",
    "        def change(x,y,mat):\n",
    "            mat[x][y] ^= 1\n",
    "            for dx, dy in (x+1, y), (x, y+1), (x-1, y), (x,y-1):\n",
    "                if 0<= dx < m and 0<= dy < n:\n",
    "                    mat[dx][dy] ^= 1\n",
    "            return mat\n",
    "\n",
    "        start = encode(mat)\n",
    "        q = [(0, start)]\n",
    "        visit = set()\n",
    "        visit.add(start)\n",
    "        while q:\n",
    "            #print(q)\n",
    "            ti, qi = heappop(q)\n",
    "            if qi == target:\n",
    "                return ti\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    matqi = decode(qi)\n",
    "                    matij = change(i,j,matqi)\n",
    "                    #print(matqi)\n",
    "                    smatij = encode(matij)\n",
    "                    if smatij not in visit:\n",
    "                        heappush(q, (ti+1, smatij))\n",
    "                        visit.add(smatij)\n",
    "                   \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        target = \"0\" * (m * n)\n",
    "        cur = ''\n",
    "        mapper = {\"0\": '1', \"1\": '0'}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cur = cur + str(mat[i][j])\n",
    "        \n",
    "        def flip(s, j):\n",
    "            s[j] = mapper[s[j]]\n",
    "            if j % n >= 1:\n",
    "                s[j-1] = mapper[s[j-1]]\n",
    "            if j % n < n-1:\n",
    "                s[j+1] = mapper[s[j+1]]\n",
    "            if j >= n:\n",
    "                s[j-n] = mapper[s[j-n]]\n",
    "            if j < (m-1) * n:\n",
    "                s[j+n] = mapper[s[j+n]]\n",
    "            return s\n",
    "\n",
    "\n",
    "        queue = [cur]\n",
    "        visited = set()\n",
    "        cnt = 0 \n",
    "        while len(queue):\n",
    "            for i in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur == target:\n",
    "                    return cnt\n",
    "                if cur in visited:\n",
    "                    continue\n",
    "                \n",
    "                visited.add(cur)\n",
    "                for j in range(len(cur)):\n",
    "                    s = list(cur)\n",
    "                    s = flip(s, j)\n",
    "                    queue.append(''.join(s))\n",
    "            cnt += 1\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        que = deque()\n",
    "        k = m * n\n",
    "        visited = set()\n",
    "        que.append((0, 0))\n",
    "        target = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                target += mat[i][j] * (1 << (i * n + j))\n",
    "        if target == 0:\n",
    "            return 0\n",
    "        while que:\n",
    "            status, step = que.popleft()\n",
    "            for i in range(k):\n",
    "                x, y = i // n, i % n\n",
    "                tmp = status\n",
    "                for dx, dy in ((0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        tmp ^= (1 << (nx * n + ny))\n",
    "                if tmp == target:\n",
    "                    return step + 1\n",
    "                if tmp not in visited:\n",
    "                    visited.add(tmp)\n",
    "                    que.append((tmp, step + 1))\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        res, m, n = inf, len(mat), len(mat[0])\n",
    "        mat, board = [reduce(lambda r, t: r + r + t, row) for row in mat], (1 << n) - 1\n",
    "        def convert(mask, i, tm):\n",
    "            if i + 1 < m: tm[i + 1] ^= mask\n",
    "            tm[i] ^= mask ^ (mask << 1) ^ (mask >> 1) \n",
    "            return tm[i] & board\n",
    "        for mask in range(1 << n):\n",
    "            tr, tm = 0, mat.copy()\n",
    "            for i in range(m):\n",
    "                tr += mask.bit_count()\n",
    "                mask = convert(mask, i, tm)\n",
    "            if mask == 0:\n",
    "                res = min(res, tr)\n",
    "                if res in (0, 1): return res\n",
    "        return res if res < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, mat, m, n):\n",
    "        x = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = x * 2 + mat[i][j]\n",
    "        return x\n",
    "    \n",
    "    def decode(self, x, m, n):\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                mat[i][j] = x & 1\n",
    "                x >>= 1\n",
    "        return mat\n",
    "    \n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]\n",
    "        for di, dj in dirs:\n",
    "            ni, nj = i + di, j + dj\n",
    "            if 0 <= ni <= m-1 and 0 <= nj <=n-1:\n",
    "                mat[ni][nj] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        x_start = self.encode(mat, m, n)\n",
    "        q = deque()\n",
    "        q.append(x_start)\n",
    "        step = 0\n",
    "        vis = set()\n",
    "        vis.add(x_start)\n",
    "\n",
    "        if x_start == 0:\n",
    "            return step\n",
    "\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                # 列表中存的是10进制\n",
    "                cur_x = q.popleft()\n",
    "                # 从当前状态中进行枚举\n",
    "                status = self.decode(cur_x, m, n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.convert(status, m, n, i, j)\n",
    "                        new_x = self.encode(status, m, n)\n",
    "                        if new_x == 0:\n",
    "                            return step\n",
    "                        if not new_x in vis:\n",
    "                            q.append(new_x)\n",
    "                            vis.add(new_x)\n",
    "                        # 需要把状态再恢复回去\n",
    "                        self.convert(status, m, n, i, j)\n",
    "        return -1\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        \n",
    "        # Convert the matrix into an integer\n",
    "        start = sum(cell << (i * n + j) for i, row in enumerate(mat) for j, cell in enumerate(row))\n",
    "        target = 0\n",
    "        \n",
    "        # Return the neighbors of a given cell\n",
    "        def neighbors(x, y):\n",
    "            for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    yield nx, ny\n",
    "        \n",
    "        # BFS search\n",
    "        queue = deque([(start, 0)])\n",
    "        seen = {start}\n",
    "        \n",
    "        while queue:\n",
    "            node, steps = queue.popleft()\n",
    "            if node == target: return steps\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    newState = node\n",
    "                    for x, y in neighbors(i, j):\n",
    "                        newState ^= 1 << (x * n + y)\n",
    "                    newState ^= 1 << (i * n + j)  # flip the cell itself\n",
    "                    if newState not in seen:\n",
    "                        seen.add(newState)\n",
    "                        queue.append((newState, steps + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gen_flips(self, mat):\n",
    "        mat = self.to_list(mat)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                _mat = copy.deepcopy(mat)\n",
    "                _mat[i][j] = 1 - _mat[i][j]\n",
    "                for dx, dy in dirs:\n",
    "                    ii = i + dx\n",
    "                    jj = j + dy\n",
    "                    if 0 <= ii < m and 0 <= jj < n:\n",
    "                        _mat[ii][jj] = 1 - _mat[ii][jj]\n",
    "                yield self.to_tuple(_mat)\n",
    "\n",
    "    def to_tuple(self, mat):\n",
    "        m = len(mat)\n",
    "        for i in range(m):\n",
    "            mat[i] = tuple(mat[i])\n",
    "        return tuple(mat)\n",
    "\n",
    "    def to_list(self, mat):\n",
    "        m = len(mat)\n",
    "        mat = list(mat)\n",
    "        for i in range(m):\n",
    "            mat[i] = list(mat[i])\n",
    "        return mat\n",
    "\n",
    "    def check(self, mat):\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        return all(mat[i][j] == 0 for i in range(m) for j in range(n))\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        q = [self.to_tuple(mat)]\n",
    "        vis = set([q[0]])\n",
    "        step = 0\n",
    "\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for m in q:\n",
    "                print(m)\n",
    "                if self.check(m):\n",
    "                    return step\n",
    "                for next_m in self.gen_flips(m):\n",
    "                    if next_m not in vis:\n",
    "                        vis.add(next_m)\n",
    "                        tmp.append(next_m)\n",
    "            q = tmp\n",
    "            step += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        def encode(mat):\n",
    "            res = 0\n",
    "            # 矩阵变二进制数\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    res = res*2+mat[i][j]\n",
    "            return res\n",
    "        def otcode(x):\n",
    "            # 二进制数变成矩阵\n",
    "            res = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    res[i][j] = x & 1\n",
    "                    x >>= 1\n",
    "            return res\n",
    "        def exchange(mat,i,j):\n",
    "            for x,y in (i,j),(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    mat[x][y] ^= 1\n",
    "        # BFS\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        q = [initial]\n",
    "        seen = {initial}\n",
    "        \n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                # 二进制数转为矩阵\n",
    "                state = otcode(x)\n",
    "                # 枚举翻转的位置\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        exchange(state,i,j)\n",
    "                        # 翻转完毕转为二进制数\n",
    "                        y = encode(state)\n",
    "                        if y == 0:return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        # 翻转回去\n",
    "                        exchange(state,i,j)\n",
    "                        \n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "\n",
    "        # 放到flip函数外部可以减少计算\n",
    "        mapper = {'0': '1', '1': '0'}\n",
    "\n",
    "        def flip(state: list[str], i: int) -> None:\n",
    "            \n",
    "            state[i] = mapper[state[i]]\n",
    "            \n",
    "            if i % n != 0:\n",
    "                state[i - 1] = mapper[state[i - 1]]\n",
    "            if i % n < n - 1:\n",
    "                state[i + 1] = mapper[state[i + 1]]\n",
    "            if i >= n:\n",
    "                state[i - n] = mapper[state[i - n]]\n",
    "            if i < (m - 1) * n:\n",
    "                state[i + n] = mapper[state[i + n]]\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        target = '0' * (m * n)\n",
    "        cur = ''.join(str(cell) for row in mat for cell in row)\n",
    "        queue = [cur]\n",
    "        visited = set()\n",
    "        steps = 0\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur == target:\n",
    "                    return steps\n",
    "                if cur in visited:\n",
    "                    continue\n",
    "                \n",
    "                visited.add(cur)\n",
    "                for i in range(len(cur)):\n",
    "                    s = list(cur)\n",
    "                    flip(s, i)\n",
    "                    queue.append(''.join(s))\n",
    "            steps += 1\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        length = m*n\n",
    "        target = [0]*length\n",
    "        cur = []\n",
    "        for ma in mat:\n",
    "            cur.extend(ma)\n",
    "        if cur == target:\n",
    "            return 0\n",
    "\n",
    "        stack = [cur]\n",
    "        visit = dict()\n",
    "        visit[tuple(cur)] = 1\n",
    "        cnt = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for pre in stack:\n",
    "                for i in range(length):\n",
    "                    cur = pre[:]\n",
    "                    r, c = i//n, i%n\n",
    "                    cur[i] = 1-cur[i]\n",
    "                    if r+1<m:\n",
    "                        cur[r*n+n+c] = 1 - cur[r*n+n+c]\n",
    "                    if r-1>=0:\n",
    "                        cur[r*n-n+c] = 1 - cur[r*n-n+c]\n",
    "                    if c+1<n:\n",
    "                        cur[r*n+c+1] = 1 - cur[r*n+c+1]\n",
    "                    if c-1>=0:\n",
    "                        cur[r*n+c-1] = 1 - cur[r*n+c-1] \n",
    "                    if tuple(cur) not in visit:\n",
    "                        nex.append(cur)\n",
    "                        visit[tuple(cur)] = 1\n",
    "                        if cur == target:\n",
    "                            return cnt\n",
    "            cnt += 1\n",
    "            stack = nex\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def encode(self, mat, m, n):\n",
    "        x = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = x * 2 + mat[i][j]\n",
    "        return x\n",
    "\n",
    "    def decode(self, x, m, n):\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                mat[i][j] = x & 1\n",
    "                x >>= 1\n",
    "        return mat\n",
    "\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        x_start, step = self.encode(mat, m, n), 0\n",
    "        if x_start == 0:\n",
    "            return step\n",
    "\n",
    "        visited = {x_start}\n",
    "        q = queue.Queue()\n",
    "        q.put_nowait(x_start)\n",
    "\n",
    "        while not q.empty():\n",
    "            step += 1\n",
    "            k = q.qsize()\n",
    "            for _ in range(k):\n",
    "                status = self.decode(q.get_nowait(), m, n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.convert(status, m, n, i, j)\n",
    "                        x_cur = self.encode(status, m, n)\n",
    "                        if x_cur == 0:\n",
    "                            return step\n",
    "                        if x_cur not in visited:\n",
    "                            visited.add(x_cur)\n",
    "                            q.put_nowait(x_cur)\n",
    "                        self.convert(status, m, n, i, j)\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        all_states = set()\n",
    "\n",
    "        def encode(mat):\n",
    "            s = \"\"\n",
    "            for m in mat:\n",
    "                for n in m:\n",
    "                    s += '0' if n == 0 else '1'\n",
    "            return s\n",
    "\n",
    "        def decode(s):\n",
    "            mat = []\n",
    "            for i in range(m):\n",
    "                lst = []\n",
    "                for j in range(n):\n",
    "                    lst.append(0 if s[n * i + j] == '0' else 1)\n",
    "                mat.append(lst)\n",
    "            return mat\n",
    "        \n",
    "        def all_next(mat):\n",
    "            states = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    states.append(flip(mat, i, j))\n",
    "            return states\n",
    "\n",
    "        def flip(mat, i, j):\n",
    "            mat = deepcopy(mat)\n",
    "            mat[i][j] = 1 - mat[i][j]\n",
    "            for x, y in get_neighbors(i, j):\n",
    "                mat[x][y] = 1 - mat[x][y]\n",
    "            return mat\n",
    "\n",
    "        def get_neighbors(i, j):\n",
    "            neighbors = []\n",
    "            for i1, j1 in ((0, -1), (0, 1), (-1, 0), (1, 0)):\n",
    "                x, y = i + i1, j + j1\n",
    "                if x >= 0 and x < m and y >= 0 and y < n:\n",
    "                    neighbors.append((x, y))\n",
    "            return neighbors\n",
    "\n",
    "        FINAL_STATE = \"0\" * (m * n)\n",
    "\n",
    "        if encode(mat) == FINAL_STATE:\n",
    "            return 0\n",
    "\n",
    "        def bfs(state: List[List[int]]):\n",
    "            q = queue.Queue()\n",
    "            steps = 0\n",
    "            q.put_nowait(encode(state))\n",
    "            while not q.empty():\n",
    "                steps += 1\n",
    "                final = False\n",
    "                q1 = queue.Queue()\n",
    "                while not q.empty():\n",
    "                    item = q.get_nowait()\n",
    "                    for nxt in all_next(decode(item)):\n",
    "                        nxt1 = encode(nxt)\n",
    "                        if nxt1 == FINAL_STATE:\n",
    "                            return steps\n",
    "                        if nxt1 not in all_states:\n",
    "                            q1.put_nowait(nxt1)\n",
    "                            all_states.add(nxt1)\n",
    "                if final:\n",
    "                    break\n",
    "                q = q1\n",
    "            return -1\n",
    "        \n",
    "        return bfs(mat)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    ans = s.minFlips([[0]])\n",
    "    print(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        searched = {}#minimum depth\n",
    "        code = self.serialize(mat)\n",
    "        stack = [(code, 0)]\n",
    "        s = 0\n",
    "        n1, n2 = len(mat), len(mat[0])\n",
    "        target = '0' * (n1 * n2)\n",
    "        while s < len(stack):\n",
    "            code, depth = stack[s]\n",
    "            if code not in searched:\n",
    "                searched[code] = depth\n",
    "            else:\n",
    "                s += 1\n",
    "                continue\n",
    "            if code == target:\n",
    "                s += 1\n",
    "                continue\n",
    "            for i in range(n1):\n",
    "                for j in range(n2):\n",
    "                    code2 = self.change(code, i, j, n1, n2)\n",
    "                    if code2 not in searched:\n",
    "                        stack.append((code2, depth + 1))\n",
    "            s += 1\n",
    "        if target in searched:\n",
    "            return searched[target]\n",
    "        else:\n",
    "            return -1 \n",
    "    \n",
    "    def change(self, code, i, j, n1, n2):\n",
    "        ks = [i * n2 + j] \n",
    "        \n",
    "        if i > 0:\n",
    "            ks.append((i-1) * n2 + j)\n",
    "        if i < n1 - 1:\n",
    "            ks.append((i+1) * n2 + j)\n",
    "        if j > 0:\n",
    "            ks.append(i * n2 + j - 1)\n",
    "        if j < n2 - 1:\n",
    "            ks.append(i * n2 + j + 1)\n",
    "        code2 = []\n",
    "        for i in range(len(code)):\n",
    "            code2.append(code[i])\n",
    "        for k in ks:\n",
    "            code2[k] = self.flip(code2[k])\n",
    "        return ''.join(code2)\n",
    "\n",
    "    def flip(self, c):\n",
    "        if c == '1':\n",
    "            return '0'\n",
    "        else:\n",
    "            return '1'\n",
    "\n",
    "    def serialize(self, matrix):\n",
    "        code = ''\n",
    "        for line in matrix:\n",
    "            code += ''.join([str(x) for x in line])\n",
    "        #code = int(code, 2)\n",
    "        return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        dq = deque([self.enconde(mat)])\n",
    "        v = set([self.enconde(mat)])\n",
    "        steps = 0\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            while size:\n",
    "                o = dq.popleft()\n",
    "                if o == 0:\n",
    "                    return steps\n",
    "                for i in range(self.m):\n",
    "                    for j in range(self.n):\n",
    "                        p = self.convert(o, i, j)\n",
    "                        # if p == 60:\n",
    "                        print(i, j, o, bin(o), bin(p))\n",
    "                        if p in v:\n",
    "                            continue\n",
    "                        dq.append(p)\n",
    "                        v.add(p)\n",
    "                size -= 1\n",
    "            steps += 1\n",
    "        return -1\n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def decode(self, num: int) -> List[List[int]]:\n",
    "        mat = [[0] * self.n for _ in range(self.m)]\n",
    "        for x in range(num.bit_length()):\n",
    "            if num & (1 << x):\n",
    "                i, j = divmod(x, self.n)\n",
    "                mat[i][j] = 1\n",
    "        return mat\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "\n",
    "        # # 同一行\n",
    "        # for y in range(i * self.n, (i + 1) * self.n):\n",
    "        #     num ^= (1 << y)\n",
    "        # # 同一列\n",
    "        # for x in range(self.m):\n",
    "        #     num ^= (1 << (x * self.n + j))\n",
    "        # num ^= (1 << (i * self.n + j))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        target = \"01\"\n",
    "        cnt = 0\n",
    "        # 010101...\n",
    "        for i in range(n):\n",
    "            if s[i] != target[i%2]:\n",
    "                cnt += 1\n",
    "        ans = min(cnt, n - cnt) # 1010...的操作次数是n - cnt\n",
    "        if n % 2 == 0: return ans  # 偶数就不用继续滑窗了，结果都一样\n",
    "\n",
    "        # 如果是奇数的情况下\n",
    "        for i in range(n):\n",
    "            if s[i] != target[i%2]:\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            ans = min(ans, cnt, n - cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        target = '01'\n",
    "        cnt = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] != target[i % 2]:\n",
    "                cnt += 1\n",
    "        ans = min(cnt, n - cnt)\n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            return ans\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] != target[i % 2]:\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            ans = min(ans, cnt, n - cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        target = '01'\n",
    "        cnt = 0\n",
    "        for i, x in enumerate(s):\n",
    "            cnt += x != target[i % 2]\n",
    "        ans = min(cnt, n - cnt)\n",
    "        for i, x in enumerate(s):\n",
    "            cnt -= x != target[i % 2]\n",
    "            cnt += x != target[(i + n) % 2]\n",
    "            ans = min(ans, cnt, n - cnt)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        even_num, odd_num = (n + 1) // 2, n // 2\n",
    "        x = s[::2].count('1') - s[1::2].count('1')\n",
    "\n",
    "        res = min(even_num - x, odd_num + x)\n",
    "\n",
    "        if n & 1 == 0:\n",
    "            return res\n",
    "        \n",
    "        for i in s:\n",
    "            x = 2 * int(i) - x\n",
    "            res = min(\n",
    "                res,\n",
    "                even_num - x,\n",
    "                odd_num + x\n",
    "            )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # 如果 n 是偶数\n",
    "        #   把字符串头尾相连，形成一个圆环（0点位置是开始位置，11点位置是结束位置）\n",
    "        #   不管进行多少次类型1操作（逆时针转动环）\n",
    "        #   都是要求环中字符0、1交替出现\n",
    "        #   所以忽略类型1操作，从头到尾0、1交替即可\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            # 分两种情况\n",
    "            #   a：第一个字符要求是 '0'\n",
    "            #   b：第一个字符要求是 '1'\n",
    "            a_count = 0\n",
    "            b_count = 0\n",
    "            a_next = '0'\n",
    "            b_next = '1'\n",
    "            for c in s:\n",
    "                if c == a_next:\n",
    "                    # 满足情况a不满足情况b\n",
    "                    b_count += 1\n",
    "                else:\n",
    "                    # 满足情况b不满足情况a\n",
    "                    a_count += 1\n",
    "                a_next, b_next = b_next, a_next\n",
    "            return min(a_count, b_count)\n",
    "\n",
    "        # 如果 n 是奇数\n",
    "        #   把字符串头尾相连，形成一个圆环（0点位置是开始位置，11点位置是结束位置）\n",
    "        #   要求字符0、1交替出现，但因为是奇数个，所以头尾必然是相同字符\n",
    "        #   执行类型1操作（逆时针转动环），就是挑选哪个位置（k）的字符，与后一个字符相等\n",
    "        #   总之从头到尾0、1交替，但要求有且只有一个位置出现连续相同字符\n",
    "\n",
    "        # 分两种情况\n",
    "        #   a：第一个字符要求是 '0' \n",
    "        #   b：第一个字符要求是 '1'\n",
    "        # a_count = [0] * n  # a_count[0] 表示 k = 0 的情况时要进行几次类型2操作\n",
    "        #                    # a_count[0] 即进行一次类型1操作，a_count[1] 即进行两次类型1操作\n",
    "        # b_count = [0] * n\n",
    "                           # b_count 其实是不用算的\n",
    "                           # b_count[0] = n - a_count[0]\n",
    "\n",
    "        a_count = 0        # 只需计算 k = 0 情况, k = 1 由 k = 0 来推算\n",
    "        for index, c in enumerate(s):\n",
    "            # 对于情况a:\n",
    "            #   如果挑选的索引位置是k（k 和 k + 1是相同字符, 如果k 为 n - 1, k + 1代表0）\n",
    "            #   <= k 时偶数索引位置应该是 '0', > k 时偶数索引位置应该是 '1'\n",
    "            #   <= k 时奇数索引位置应该是 '1', > k 时奇数索引位置应该是 '0'\n",
    "            # 对于情况b: 正好相反\n",
    "            #   <= k 时偶数索引位置应该是 '1', > k 时偶数索引位置应该是 '0'\n",
    "            #   <= k 时奇数索引位置应该是 '0', > k 时奇数索引位置应该是 '1'\n",
    "            if (index == 0 or index & 1 == 1):\n",
    "                if c == '1':\n",
    "                    a_count += 1\n",
    "            else:\n",
    "                if c == '0':\n",
    "                    a_count += 1\n",
    "\n",
    "        rs = min(a_count, n - a_count)\n",
    "\n",
    "        # a_count[k] 和 a_count[k + 1] 就只是变了 s[k+1] 这个字符\n",
    "        for k in range(1, n):\n",
    "            if k & 1 == 1:\n",
    "                # k是奇数, s[k] 要变为1\n",
    "                if s[k] == '1':\n",
    "                    a_count -= 1\n",
    "                else:\n",
    "                    a_count += 1\n",
    "            else:\n",
    "                # k是偶数, s[k] 要变为0\n",
    "                if s[k] == '0':\n",
    "                    a_count -= 1\n",
    "                else:\n",
    "                    a_count += 1\n",
    "            _min = min(a_count, n - a_count)\n",
    "            if _min < rs:\n",
    "                rs = _min\n",
    "\n",
    "        return rs\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minFlips(self, s: str) -> int:\r\n",
    "        n = len(s) \r\n",
    "        cur = '1'\r\n",
    "        cnt = 0\r\n",
    "        for x in s:\r\n",
    "            if x == cur:\r\n",
    "                cnt += 1\r\n",
    "            cur = '0' if cur == '1' else '1'\r\n",
    "        if n % 2 == 0:\r\n",
    "            return min(cnt, n - cnt) \r\n",
    "        res = inf \r\n",
    "        for x in s:\r\n",
    "            if x == '1':\r\n",
    "                cnt = n - (cnt - 1) \r\n",
    "            else:\r\n",
    "                cnt = n - (cnt + 1) \r\n",
    "            res = min(res, cnt, n - cnt) \r\n",
    "        return res \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        target = '01'\n",
    "        n, cnt = len(s), 0\n",
    "        for i in range(n):\n",
    "            if s[i] != target[i % 2]:\n",
    "                cnt += 1\n",
    "        min_v = min(cnt, n - cnt)\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            return min_v\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == target[i % 2]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            min_v = min(min_v, cnt, n - cnt)\n",
    "        return min_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        ans0 = ans1 = 0\n",
    "        for i, c in enumerate(s): # O(n), O(1)\n",
    "            if (i % 2 == 1) ^ (c == \"0\"):\n",
    "                ans1 += 1\n",
    "            else:\n",
    "                ans0 += 1\n",
    "        \n",
    "        ans = min(ans0, ans1)\n",
    "        if len(s) % 2:\n",
    "            for i in range(len(s)-1): # O(n), O(1)\n",
    "                if s[i] == \"0\":\n",
    "                    ans0, ans1 = ans1-1, ans0+1\n",
    "                else:\n",
    "                    ans0, ans1 = ans1+1, ans0-1\n",
    "                ans = min(ans, ans0, ans1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right - n if right >= n else right]\n",
    "            if int(x) != f:\n",
    "                cnt += 1\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if int(s[left]) != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right - left +1 == n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = (f + 1) % 2\n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        target = '01'\n",
    "        n, count = len(s), 0\n",
    "        for i in range(n):\n",
    "            if s[i] != target[i%2]:\n",
    "                count += 1\n",
    "        minv = min(count, n-count)\n",
    "        if n % 2 == 0:\n",
    "            return minv\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] == target[i % 2]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            minv = min(minv, count, n-count)\n",
    "        return minv\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            if int(x) != f:\n",
    "                cnt += 1\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if int(s[left]) != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right - left +1 == n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = (f + 1) % 2\n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        target = '01'\n",
    "        left = right = cnt = 0\n",
    "        ans = n = len(s)\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            cnt += x != target[right % 2]\n",
    "            if right >= n:\n",
    "                cnt -= s[left] != target[left % 2]\n",
    "                left += 1\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # 如果 n 是偶数\n",
    "        #   把字符串头尾相连，形成一个圆环（0点位置是开始位置，11点位置是结束位置）\n",
    "        #   不管进行多少次类型1操作（逆时针转动环）\n",
    "        #   都是要求环中字符0、1交替出现\n",
    "        #   所以忽略类型1操作，从头到尾0、1交替即可\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            # 分两种情况\n",
    "            #   a：第一个字符要求是 '0'\n",
    "            #   b：第一个字符要求是 '1'\n",
    "            a_count = 0\n",
    "            b_count = 0\n",
    "            a_next = '0'\n",
    "            b_next = '1'\n",
    "            for c in s:\n",
    "                if c == a_next:\n",
    "                    # 满足情况a不满足情况b\n",
    "                    b_count += 1\n",
    "                # else:\n",
    "                #     # 满足情况b不满足情况a\n",
    "                #     a_count += 1\n",
    "                a_next, b_next = b_next, a_next\n",
    "            # return min(a_count, b_count)\n",
    "            return min(b_count, n - b_count)\n",
    "\n",
    "        # 如果 n 是奇数\n",
    "        #   把字符串头尾相连，形成一个圆环（0点位置是开始位置，11点位置是结束位置）\n",
    "        #   要求字符0、1交替出现，但因为是奇数个，所以头尾必然是相同字符\n",
    "        #   执行类型1操作（逆时针转动环），就是挑选哪个位置（k）的字符，与后一个字符相等\n",
    "        #   总之从头到尾0、1交替，但要求有且只有一个位置出现连续相同字符\n",
    "\n",
    "        # 分两种情况\n",
    "        #   a：第一个字符要求是 '0' \n",
    "        #   b：第一个字符要求是 '1'\n",
    "        # a_count = [0] * n  # a_count[0] 表示 k = 0 的情况时要进行几次类型2操作\n",
    "        #                    # a_count[0] 即进行一次类型1操作，a_count[1] 即进行两次类型1操作\n",
    "        # b_count = [0] * n\n",
    "                           # b_count 其实是不用算的\n",
    "                           # b_count[0] = n - a_count[0]\n",
    "                           # b_count[1] = n - a_count[1]\n",
    "        # 对于情况a:\n",
    "            #   如果挑选的索引位置是k（k 和 k + 1是相同字符, 如果k 为 n - 1, k + 1代表0）\n",
    "            #   <= k 时偶数索引位置应该是 '0', > k 时偶数索引位置应该是 '1'\n",
    "            #   <= k 时奇数索引位置应该是 '1', > k 时奇数索引位置应该是 '0'\n",
    "\n",
    "        # 进一步优化：只需计算 k = 0 情况, k = 1 由 k = 0 来推算\n",
    "        # k = 0: \"00101\"\n",
    "        # k = 1: \"01101\"\n",
    "        # k = 0 和 k = 1 只是将 s[k=1] 转换为 1 即可\n",
    "        # 如果 s[1] 原本为0 则 a_count[1] = a_count[0] + 1\n",
    "        # 如果 s[1] 原本为1 则 a_count[1] = a_count[0] - 1\n",
    "        a_count = 0        # 计算a情况下 k = 0 时需要几次类型2操作\n",
    "        for index, c in enumerate(s):\n",
    "            if (index == 0 or index & 1 == 1):\n",
    "                if c == '1':\n",
    "                    a_count += 1\n",
    "            else:\n",
    "                if c == '0':\n",
    "                    a_count += 1\n",
    "\n",
    "        rs = min(a_count, n - a_count)\n",
    "\n",
    "        # a_count[k] 和 a_count[k + 1] 就只是变了 s[k+1] 这个字符\n",
    "        for k in range(1, n):\n",
    "            if k & 1 == 1:\n",
    "                # k是奇数, s[k] 要变为1\n",
    "                if s[k] == '1':\n",
    "                    a_count -= 1\n",
    "                else:\n",
    "                    a_count += 1\n",
    "            else:\n",
    "                # k是偶数, s[k] 要变为0\n",
    "                if s[k] == '0':\n",
    "                    a_count -= 1\n",
    "                else:\n",
    "                    a_count += 1\n",
    "            _min = min(a_count, n - a_count)\n",
    "            if _min < rs:\n",
    "                rs = _min\n",
    "\n",
    "        return rs\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        t={'0':'1','1':'0'}\n",
    "        #正难则反，类型二最少等价于求类型一最多操作次数\n",
    "        #类型一等价于翻转字符串\n",
    "        #奇偶性\n",
    "        tag='01'\n",
    "        n=len(s)\n",
    "        cnt=0\n",
    "        res=inf\n",
    "        for i in range(n):\n",
    "            cnt+=(s[i]!=tag[i%2])\n",
    "        res=min(cnt,n-cnt)\n",
    "        for i in range(n):\n",
    "            cnt-=(s[i]!=tag[i%2])\n",
    "            cnt+=(s[i]!=tag[(i+n)%2])\n",
    "            res=min(res,cnt,n-cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        taget = '01'\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] != taget[i%2]:\n",
    "                cnt += 1\n",
    "        print(cnt)\n",
    "        ans = min(cnt, n - cnt)\n",
    "\n",
    "        if n % 2 == 0: return ans\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == taget[i %2]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            ans = min(ans, cnt, n - cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        odd_one = 0\n",
    "        even_one = 0\n",
    "        n = len(s)\n",
    "        for index, char in enumerate(s):\n",
    "            if char == '1':\n",
    "                if index % 2 == 0:\n",
    "                    even_one += 1\n",
    "                else:\n",
    "                    odd_one += 1\n",
    "\n",
    "        res = min((n + 1) / 2 - even_one + odd_one, even_one + n / 2 - odd_one)\n",
    "\n",
    "        for index in range(n - 1):\n",
    "            odd_one, even_one = even_one, odd_one\n",
    "            if s[index] == '1' and n & 1:\n",
    "                odd_one -= 1\n",
    "                even_one += 1\n",
    "            \n",
    "            res = min(res, (n + 1) / 2 - even_one + odd_one, even_one + n / 2 - odd_one)\n",
    "        \n",
    "        return int(res)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        x = sum(int(s[i]) != i%2 for i in range(n)) # to 0101...\n",
    "        ans = min(x, n-x)\n",
    "        y = 0\n",
    "        for i in range(n-1):\n",
    "            a = (int(s[i]) != i%2)\n",
    "            y += a\n",
    "            x -= a\n",
    "            x0 = x if (i+1)%2 == 0 else n-1-i-x\n",
    "            if (n-i-1) % 2 == 0:\n",
    "                ans = min(ans, x0+y, n-x0-y)\n",
    "            else:\n",
    "                ans = min(ans, x0 + i+1-y, n-x0-i-1+y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "\n",
    "        # 本题我的思考难点: 对于类型1的操作无法想清楚什么情况下去执行才能贪心到开销最小；对于交替字符串只会枚举0开头和1开头的然后算开销。\n",
    "        # 类型一：2倍字符串 滑动窗口\n",
    "\n",
    "        n = len(s)\n",
    "        res = inf\n",
    "        l = sm = 0\n",
    "        s *= 2\n",
    "        x = 0 # 当前位需配对x\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            c = int(c)\n",
    "            sm += ((c ^ x) == 1) # 当前位不匹配x时，修改次数+1\n",
    "            while i - l + 1 > n:\n",
    "                if ((n + 1) & 1) == 0:\n",
    "                    sm -= ((int(s[l]) ^ (x ^ 1)) == 1)\n",
    "                else:\n",
    "                    sm -= ((int(s[l]) ^ x) == 1)\n",
    "                l += 1\n",
    "            if i - l + 1 == n:\n",
    "                # 同时考虑0开头和1开头的修改次数\n",
    "                res = min(res, sm, n - sm)\n",
    "            x ^= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        target = '01'\n",
    "        diff = 0\n",
    "        for i in range(n):\n",
    "            if s[i]!=target[i%2]:\n",
    "                diff+=1\n",
    "        res = min(diff,n-diff)\n",
    "        \n",
    "        for left in range(n):   # left表示现在左边界的左邻居（被删的）\n",
    "            diff -= int(s[left] != target[left%2])\n",
    "            diff += int(s[left] != target[(left+n)%2])    # left相当于现在的右边界\n",
    "            res = min(res,diff,n-diff)    # n-min_val就是与10101010...差别的个数\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        result = min((count := sum(c != (target := '01')[i & 1] for i, c in enumerate(s))), (n := len(s)) - count)\n",
    "        for i, c in enumerate(s):\n",
    "            result = min(result, (count := count + (s[i] != target[(i + n) & 1]) - (s[i] != target[i & 1])), n - count)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        # Function to calculate the initial number of flips\n",
    "        def initial_calculation(s: str) -> int:\n",
    "            cnt = 0  # Initialize the mismatch counter to zero\n",
    "            for i in range(len(s)):\n",
    "                # Check for each character if it matches the character at the corresponding position in the target string\n",
    "                if s[i] != str(i % 2):  \n",
    "                    cnt += 1  # Increase the counter if it does not match\n",
    "            return cnt\n",
    "        \n",
    "        # Function to update the number of flips using sliding window\n",
    "        def sliding_window_update(s: str, initial_flips: int) -> int:\n",
    "            n = len(s)\n",
    "            ans = min(initial_flips, n - initial_flips)  # Initialize the result variable ans\n",
    "            \n",
    "            # Use a loop to update the number of mismatches by sliding the window\n",
    "            for i in range(1, n):\n",
    "                # Subtract mismatches of characters on the left side of the window\n",
    "                if s[i - 1] != str((i - 1) % 2):\n",
    "                    initial_flips -= 1\n",
    "                # Add mismatches to the characters on the right side of the window\n",
    "                if s[(i + n - 1) % n] != str((i + n - 1) % 2):\n",
    "                    initial_flips += 1\n",
    "                \n",
    "                # After each step update, compare the current number of mismatches with its complement\n",
    "                # and the previous minimum number of flips, update the minimum number of flips ans\n",
    "                ans = min(ans, min(initial_flips, n - initial_flips))\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        # Calculate the initial number of flips\n",
    "        initial_flips = initial_calculation(s)\n",
    "        \n",
    "        # Update the number of flips using sliding window\n",
    "        result = sliding_window_update(s, initial_flips)\n",
    "        \n",
    "        return result\n",
    "\n",
    "# Example usage:\n",
    "# solution = Solution()\n",
    "# result = solution.minFlips(\"010\")\n",
    "# print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        head_0 = 0\n",
    "        head_1 = 0\n",
    "        for i in range(n):\n",
    "            res = int(s[i] == '0')\n",
    "            if i % 2 == 0:\n",
    "                head_0 += (1 - res)\n",
    "                head_1 += res\n",
    "            else:\n",
    "                head_0 += res\n",
    "                head_1 += (1 - res)\n",
    "        if n % 2 == 0:\n",
    "            return min(head_0, head_1)\n",
    "        ans = min(head_0, head_1)\n",
    "        for i in range(n - 1):\n",
    "            tmp = head_0\n",
    "            head_0 = head_1 - int(s[i] == '0') + int(s[i] == '1')\n",
    "            head_1 = tmp - int(s[i] == '1') + int(s[i] == '0')\n",
    "            ans = min(ans, head_0, head_1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        a=\"01\"\n",
    "        n=len(s)\n",
    "        con=0\n",
    "        for i in range(n):\n",
    "            if s[i]==a[i%2]:\n",
    "                con+=1\n",
    "        ans=min(con,n-con)\n",
    "        s+=s\n",
    "        for i in range(n):\n",
    "            if s[i]==a[i%2]:\n",
    "                con-=1\n",
    "            if s[i+n]==a[(i+n)%2]:\n",
    "                con+=1\n",
    "            ans=min(ans,con,n-con)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + s\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        for right, x in enumerate(s):\n",
    "            if int(x) != f:\n",
    "                cnt += 1\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if int(s[left]) != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right - left +1 == n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = (f + 1) % 2\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s, start):\n",
    "        x, n, s0 = 0, len(s)//2, start*(len(s)//2)\n",
    "        res = x = sum(i != j for i, j in zip(s[:n], s0))\n",
    "        for i in range(n):\n",
    "            x += (s0[i+n]!=s[i+n]) - (s0[i]!=s[i])\n",
    "            res = min(x, res)\n",
    "        return res\n",
    "            \n",
    "    def minFlips(self, s: str) -> int:\n",
    "        return min(self.f(2*s, '01'), self.f(2*s, '10'))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        s = s + s\n",
    "        s1 = '10' * (len(s) // 2) + '1' * (len(s) % 2)\n",
    "        s2 = '01' * (len(s) // 2) + '0' * (len(s) % 2)\n",
    "        diff1 = diff2 = 0\n",
    "        res = len(s)\n",
    "        l = 0\n",
    "        for r in range(len(s)):\n",
    "            if s[r] != s1[r]: diff1 += 1\n",
    "            if s[r] != s2[r]: diff2 += 1\n",
    "\n",
    "            if r >= len(s) / 2:\n",
    "                if s[l] != s1[l]: diff1 -= 1\n",
    "                if s[l] != s2[l]: diff2 -= 1\n",
    "                l += 1\n",
    "                res = min(res, diff1, diff2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Double the string to simulate circularity\n",
    "        target1 = '01' * n  # Expected alternating pattern 010101...\n",
    "        target2 = '10' * n  # Expected alternating pattern 101010...\n",
    "        \n",
    "        diff1 = diff2 = 0\n",
    "        min_flips = float('inf')\n",
    "        \n",
    "        # Count the differences between the original string and the two targets\n",
    "        for i in range(2 * n):\n",
    "            if s[i] != target1[i]:\n",
    "                diff1 += 1\n",
    "            if s[i] != target2[i]:\n",
    "                diff2 += 1\n",
    "            \n",
    "            # Maintain a sliding window of size n\n",
    "            if i >= n:\n",
    "                if s[i - n] != target1[i - n]:\n",
    "                    diff1 -= 1\n",
    "                if s[i - n] != target2[i - n]:\n",
    "                    diff2 -= 1\n",
    "            \n",
    "            # Update the minimum flips needed\n",
    "            if i >= n - 1:\n",
    "                min_flips = min(min_flips, min(diff1, diff2))\n",
    "        \n",
    "        return min_flips\n",
    "\n",
    "# Example usage:\n",
    "solution = Solution()\n",
    "s = \"001011101\"\n",
    "result = solution.minFlips(s)\n",
    "print(result)  # Output: 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string with itself to consider circular shifts\n",
    "        target_patterns = ['01' * n, '10' * n]  # Alternating patterns\n",
    "        \n",
    "        min_flips = float('inf')\n",
    "        for target in target_patterns:\n",
    "            flips_needed = 0\n",
    "            for i in range(n):\n",
    "                if s[i] != target[i]:\n",
    "                    flips_needed += 1\n",
    "            min_flips = min(min_flips, flips_needed)\n",
    "            \n",
    "            for i in range(n, 2 * n):\n",
    "                if s[i - n] != target[i - n]:\n",
    "                    flips_needed -= 1\n",
    "                if s[i] != target[i]:\n",
    "                    flips_needed += 1\n",
    "                min_flips = min(min_flips, flips_needed)\n",
    "                \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"010101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # This will output the minimum number of flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + s  # Double the string to handle cyclic rotations\n",
    "        ans = float('inf')\n",
    "        \n",
    "        # Create two templates for odd and even starting positions\n",
    "        template1 = '01' * n\n",
    "        template2 = '10' * n\n",
    "        \n",
    "        diff1, diff2 = 0, 0\n",
    "        \n",
    "        # Count differences between s and templates for both cases\n",
    "        for i in range(n):\n",
    "            if s[i] != template1[i]:\n",
    "                diff1 += 1\n",
    "            if s[i] != template2[i]:\n",
    "                diff2 += 1\n",
    "        \n",
    "        ans = min(diff1, diff2)\n",
    "        \n",
    "        # Slide the window to find the minimum flips\n",
    "        for i in range(n, 2 * n):\n",
    "            if s[i - n] != template1[i - n]:\n",
    "                diff1 -= 1\n",
    "            if s[i] != template1[i]:\n",
    "                diff1 += 1\n",
    "            \n",
    "            if s[i - n] != template2[i - n]:\n",
    "                diff2 -= 1\n",
    "            if s[i] != template2[i]:\n",
    "                diff2 += 1\n",
    "            \n",
    "            ans = min(ans, diff1, diff2)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# Test the code\n",
    "s = \"001011101\"\n",
    "solution = Solution()\n",
    "result = solution.minFlips(s)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Duplicate the string to handle circular shifts\n",
    "        alt1, alt2 = \"01\" * n, \"10\" * n  # Two possible alternating patterns\n",
    "\n",
    "        # Count the number of differences between s and the alternating patterns\n",
    "        diff1 = diff2 = 0\n",
    "        for i in range(n):\n",
    "            if s[i] != alt1[i]:\n",
    "                diff1 += 1\n",
    "            if s[i] != alt2[i]:\n",
    "                diff2 += 1\n",
    "\n",
    "        min_diff = min(diff1, diff2)\n",
    "\n",
    "        # Iterate over the remaining positions\n",
    "        for i in range(n, 2 * n):\n",
    "            # Update the differences due to circular shift\n",
    "            if s[i - n] != alt1[i - n]:\n",
    "                diff1 -= 1\n",
    "            if s[i - n] != alt2[i - n]:\n",
    "                diff2 -= 1\n",
    "\n",
    "            if s[i] != alt1[i]:\n",
    "                diff1 += 1\n",
    "            if s[i] != alt2[i]:\n",
    "                diff2 += 1\n",
    "\n",
    "            min_diff = min(min_diff, diff1, diff2)\n",
    "\n",
    "        return min_diff\n",
    "\n",
    "# Example usage:\n",
    "solution = Solution()\n",
    "binary_string = \"010101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output: 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(map(int, s))\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            if x != f:\n",
    "                cnt += 1\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if s[left] != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right >= n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = 0 if f else 1 \n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        s = list(map(int, s))\n",
    "        left = right = cnt = f = 0\n",
    "        ans = n = len(s)\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            cnt += x != f\n",
    "            if right >= n:\n",
    "                cnt -= s[left] != (f + n) % 2\n",
    "                left += 1\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f ^= 1\n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(map(int, s))\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            cnt += x != f\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if s[left] != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right >= n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = 0 if f else 1 \n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        # Count the number of characters that need to be flipped in an alternating pattern\n",
    "        count_to_flip = sum([1 if s[i] == str(i % 2) else 0 for i in range(n)])\n",
    "        # Count the number of characters that need to be flipped in the opposite alternating pattern\n",
    "        count_to_flip_opposite = sum([1 if s[i] == str((i + 1) % 2) else 0 for i in range(n)])\n",
    "        \n",
    "        # Initialize the answer with the minimum of the two counts\n",
    "        min_flips = min(count_to_flip, count_to_flip_opposite)\n",
    "        \n",
    "        # Iterate through the string with a sliding window approach\n",
    "        for i in range(n):\n",
    "            # Update the counts for the sliding window\n",
    "            count_to_flip -= (s[i] == str(i % 2))\n",
    "            count_to_flip_opposite -= (s[i] == str((i + 1) % 2))\n",
    "            \n",
    "            # Determine the ending index of the current window\n",
    "            end_idx = i + n\n",
    "            \n",
    "            # Calculate the index of the character that should be at the end of the current window\n",
    "            char_to_match = str((end_idx + 1) % 2)\n",
    "            \n",
    "            # Update the counts based on the character at the end of the window\n",
    "            count_to_flip_opposite += (s[end_idx % n] == char_to_match)\n",
    "            count_to_flip += (s[end_idx % n] != char_to_match)\n",
    "            \n",
    "            # Update the minimum flips with the current window's minimum\n",
    "            min_flips = min(min_flips, min(count_to_flip, count_to_flip_opposite))\n",
    "        \n",
    "        return min_flips\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(map(int, s))\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            if x != f:\n",
    "                cnt += 1\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if s[left] != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right - left +1 == n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = 0 if f else 1 \n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        s = list(map(int, s))\n",
    "        left = right = cnt = f = 0\n",
    "        ans = n = len(s)\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            cnt += x != f\n",
    "            if right >= n:\n",
    "                cnt -= s[left] != (f + n) % 2\n",
    "                left += 1\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = 0 if f else 1 \n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        s = list(map(int, s))\n",
    "        left = right = cnt = f = 0\n",
    "        ans = n = len(s)\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            cnt += x != f\n",
    "            if right >= n:\n",
    "                cnt -= s[left] != (f + n) % 2\n",
    "                left += 1\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = 0 if f else 1 \n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(map(int, s))\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            cnt += x != f\n",
    "            if right >= n:\n",
    "                lf = (f + n) % 2 \n",
    "                if s[left] != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = 0 if f else 1 \n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(map(int, s))\n",
    "        left = right = 0\n",
    "        cnt = 0\n",
    "        f = 0\n",
    "        ans = n\n",
    "        while right < 2 * n:\n",
    "            x = s[right % n]\n",
    "            if x != f:\n",
    "                cnt += 1\n",
    "            while right - left + 1 > n:\n",
    "                lf = (f + n) % 2 \n",
    "                if s[left] != lf:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            if right - left +1 == n:\n",
    "                ans = min(ans, cnt, n - cnt)\n",
    "            f = (f + 1) % 2\n",
    "            right += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        # Calculate the initial count of characters that need flipping to achieve an alternate pattern\n",
    "        initial_count = sum([s[i] == str(i % 2) for i in range(n)])\n",
    "        min_flips = min(initial_count, n - initial_count)\n",
    "        \n",
    "        # Use sliding window to find the minimum flips\n",
    "        for i in range(1, n + 1):\n",
    "            # Update the character flip count for the current window\n",
    "            initial_count -= s[i - 1] == str((i - 1) % 2)\n",
    "            initial_count += s[(i + n - 1) % n] == str((i + n - 1) % 2)\n",
    "            \n",
    "            # Update the minimum flip count\n",
    "            min_flips = min(min_flips, min(initial_count, n - initial_count))\n",
    "        \n",
    "        return min_flips\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        # Count the number of characters that need to be flipped in an alternating pattern\n",
    "        count_to_flip = sum([1 if s[i] == str(i % 2) else 0 for i in range(n)])\n",
    "        # Count the number of characters that need to be flipped in the opposite alternating pattern\n",
    "        count_to_flip_opposite = sum([1 if s[i] == str((i + 1) % 2) else 0 for i in range(n)])\n",
    "        \n",
    "        # Initialize the answer with the minimum of the two counts\n",
    "        min_flips = min(count_to_flip, count_to_flip_opposite)\n",
    "        \n",
    "        # Iterate through the string with a sliding window approach\n",
    "        for i in range(n):\n",
    "            # Update the counts for the sliding window\n",
    "            count_to_flip -= (s[i] == str(i % 2))\n",
    "            count_to_flip_opposite -= (s[i] == str((i + 1) % 2))\n",
    "            \n",
    "            # Determine the ending index of the current window\n",
    "            end_idx = i + n\n",
    "            \n",
    "            # Calculate the index of the character that should be at the end of the current window\n",
    "            char_to_match = str((end_idx + 1) % 2)\n",
    "            \n",
    "            # Update the counts based on the character at the end of the window\n",
    "            count_to_flip_opposite += (s[end_idx % n] == char_to_match)\n",
    "            count_to_flip += (s[end_idx % n] != char_to_match)\n",
    "            \n",
    "            # Update the minimum flips with the current window's minimum\n",
    "            min_flips = min(min_flips, min(count_to_flip, count_to_flip_opposite))\n",
    "        \n",
    "        return min_flips\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        # Count the number of characters that need to be flipped in an alternating pattern\n",
    "        count_to_flip = sum([1 if s[i] == str(i % 2) else 0 for i in range(n)])\n",
    "        # Count the number of characters that need to be flipped in the opposite alternating pattern\n",
    "        count_to_flip_opposite = sum([1 if s[i] == str((i + 1) % 2) else 0 for i in range(n)])\n",
    "        \n",
    "        # Initialize the answer with the minimum of the two counts\n",
    "        min_flips = min(count_to_flip, count_to_flip_opposite)\n",
    "        \n",
    "        # Iterate through the string with a sliding window approach\n",
    "        for i in range(n):\n",
    "            # Update the counts for the sliding window\n",
    "            count_to_flip -= (s[i] == str(i % 2))\n",
    "            count_to_flip_opposite -= (s[i] == str((i + 1) % 2))\n",
    "            \n",
    "            # Determine the ending index of the current window\n",
    "            end_idx = i + n\n",
    "            \n",
    "            # Calculate the index of the character that should be at the end of the current window\n",
    "            char_to_match = str((end_idx + 1) % 2)\n",
    "            \n",
    "            # Update the counts based on the character at the end of the window\n",
    "            count_to_flip_opposite += (s[end_idx % n] == char_to_match)\n",
    "            count_to_flip += (s[end_idx % n] != char_to_match)\n",
    "            \n",
    "            # Update the minimum flips with the current window's minimum\n",
    "            min_flips = min(min_flips, min(count_to_flip, count_to_flip_opposite))\n",
    "        \n",
    "        return min_flips\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        # Count the number of characters that need to be flipped in an alternating pattern\n",
    "        count_to_flip = sum([1 if s[i] == str(i % 2) else 0 for i in range(n)])\n",
    "        # Count the number of characters that need to be flipped in the opposite alternating pattern\n",
    "        count_to_flip_opposite = sum([1 if s[i] == str((i + 1) % 2) else 0 for i in range(n)])\n",
    "        \n",
    "        # Initialize the answer with the minimum of the two counts\n",
    "        min_flips = min(count_to_flip, count_to_flip_opposite)\n",
    "        \n",
    "        # Iterate through the string with a sliding window approach\n",
    "        for i in range(n):\n",
    "            # Update the counts for the sliding window\n",
    "            count_to_flip -= (s[i] == str(i % 2))\n",
    "            count_to_flip_opposite -= (s[i] == str((i + 1) % 2))\n",
    "            \n",
    "            # Determine the ending index of the current window\n",
    "            end_idx = i + n\n",
    "            \n",
    "            # Calculate the index of the character that should be at the end of the current window\n",
    "            char_to_match = str((end_idx + 1) % 2)\n",
    "            \n",
    "            # Update the counts based on the character at the end of the window\n",
    "            count_to_flip_opposite += (s[end_idx % n] == char_to_match)\n",
    "            count_to_flip += (s[end_idx % n] != char_to_match)\n",
    "            \n",
    "            # Update the minimum flips with the current window's minimum\n",
    "            min_flips = min(min_flips, min(count_to_flip, count_to_flip_opposite))\n",
    "        \n",
    "        return min_flips\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        cnt0, cnt1 = 0, 0\n",
    "        num0, num1 = 0, 1\n",
    "        p0, p1 = '', ''\n",
    "        for c in s:\n",
    "            if int(c) != num0: cnt0 += 1\n",
    "            if int(c) != num1: cnt1 += 1\n",
    "            p0 += str(num0)\n",
    "            p1 += str(num1)\n",
    "            num0 = 1 - num0\n",
    "            num1 = 1 - num1\n",
    "        ans = min(cnt0, cnt1)\n",
    "        n = len(s)\n",
    "        s *= 2\n",
    "        for i in range(n):\n",
    "            if s[i] != p0[i]: cnt0 -= 1\n",
    "            if s[i] != p1[i]: cnt1 -= 1\n",
    "            if s[i+n] != str(num0): cnt0 += 1\n",
    "            if s[i+n] != str(num1): cnt1 += 1           \n",
    "            ans = min((ans, cnt0, cnt1))\n",
    "            num0 = 1 - num0\n",
    "            num1 = 1 - num1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s, start):\n",
    "        x, n, s0 = 0, len(s)//2, start\n",
    "        for i in range(len(s)):\n",
    "            start = '01'[start=='0']\n",
    "            s0 += start     \n",
    "        res = x = sum(i != j for i, j in zip(s[:n], s0))\n",
    "        for i in range(n):\n",
    "            x += (s0[i+n]!=s[i+n]) - (s0[i]!=s[i])\n",
    "            res = min(x, res)\n",
    "        return res\n",
    "            \n",
    "\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        return min(self.f(2*s, '0'), self.f(2*s, '1'))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        extended = s + s\n",
    "        target1, target2 = \"\", \"\"\n",
    "\n",
    "        for i in range(2*n):\n",
    "            target1 += '0' if i % 2 == 0 else '1'\n",
    "            target2 += '1' if i % 2 == 0 else '0'\n",
    "\n",
    "        count0 = 0\n",
    "        count1 = 0\n",
    "\n",
    "        minf = float('inf')\n",
    "\n",
    "        for i in range(2*n):\n",
    "            if extended[i] != target1[i]:\n",
    "                count0 += 1\n",
    "            if extended[i] != target2[i]:\n",
    "                count1 += 1\n",
    "            if i >= n:\n",
    "                if extended[i-n] != target1[i-n]:\n",
    "                    count0 -= 1\n",
    "                if extended[i-n] != target2[i-n]:\n",
    "                    count1 -= 1\n",
    "            if i >= n - 1:\n",
    "                minf = min(count0, count1, minf)\n",
    "        return minf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + s\n",
    "        alter1, alter2 = \"\", \"\"\n",
    "        for i in range(2*n):\n",
    "            if i % 2 == 0:\n",
    "                alter1 += \"0\"\n",
    "                alter2 += \"1\"\n",
    "            else:\n",
    "                alter1 += \"1\"\n",
    "                alter2 += \"0\"\n",
    "        l, res = 0, n\n",
    "        diff1, diff2 = 0, 0\n",
    "        for r in range(2*n):\n",
    "            if s[r] != alter1[r]:\n",
    "                diff1 += 1\n",
    "            else:\n",
    "                diff2 += 1\n",
    "            #judge if need to shrink the window\n",
    "            if r - l + 1 > n:\n",
    "                if s[l] != alter1[l]:\n",
    "                    diff1 -= 1\n",
    "                else:\n",
    "                    diff2 -= 1\n",
    "                l += 1\n",
    "            #if the window is valid, update the res\n",
    "            if r - l + 1 == n:\n",
    "                res = min(res, diff1, diff2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + s\n",
    "        alter1, alter2 = \"\", \"\"\n",
    "        for i in range(2*n):\n",
    "            if i % 2 == 0:\n",
    "                alter1 += \"0\"\n",
    "                alter2 += \"1\"\n",
    "            else:\n",
    "                alter1 += \"1\"\n",
    "                alter2 += \"0\"\n",
    "        l, res = 0, n\n",
    "        diff1, diff2 = 0, 0\n",
    "        for r in range(2*n):\n",
    "            if s[r] != alter1[r]:\n",
    "                diff1 += 1\n",
    "            else:\n",
    "                diff2 += 1\n",
    "            #judge if need to shrink the window\n",
    "            if r - l + 1 > n:\n",
    "                if s[l] != alter1[l]:\n",
    "                    diff1 -= 1\n",
    "                else:\n",
    "                    diff2 -= 1\n",
    "                l += 1\n",
    "            #if the window is valid, update the res\n",
    "            if r - l + 1 == n:\n",
    "                res = min(res, diff1, diff2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        這題看兩次還看不懂題目...\n",
    "        \n",
    "        給一個 binary string: s, 可以做以下兩個操作\n",
    "        1. 把 s 的最左邊換到最右邊(這個可以做無限次)\n",
    "        2. 任意的 bit 0/1 互換(要求最小次數)\n",
    "        \n",
    "        找出可以讓 s 變成 alternating 的最小 bit 反轉次數\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "        alternating 的意思是: 下一個 bit 就反轉\n",
    "        例如:\n",
    "        \n",
    "        s = 1110000\n",
    "        先有 s, len(s) = 6\n",
    "        長度為 6 的 alternating 有兩種:\n",
    "        \n",
    "        alt1: 010101\n",
    "        alt2: 101010\n",
    "        \n",
    "        題目的意思就是說\n",
    "        找出能夠可以讓 s 變成上面兩個(其中一個)的最小 bit 反轉次數\n",
    "        \n",
    "        想法:\n",
    "        s 和 alt1, alt2 做\"比較\"不是問題, 找出 diff1, diff2 取最小值\n",
    "        但我們需要把 \"remove & append\" 這件事情加進來\n",
    "        因為移動 bit 這件事情是有限的操作, 做個 len(s) 次就恢復原狀了\n",
    "        所以把 s = s + s 把 s 擴充成兩段\n",
    "        alt1, alt2 也擴充成兩段\n",
    "        \n",
    "        使用 sliding window 從左邊移動到右邊, 找出最小的 diff\n",
    "        (如果沒有先把 s = s + s, 那我們就得一個個往右邊塞入, 這樣會花更多時間)\n",
    "        \"\"\"\n",
    "        \n",
    "        n = len(s)\n",
    "        s = s + s\n",
    "        alt1, alt2 = \"\", \"\"\n",
    "        \n",
    "        for i in range(len(s)): # 把 s 擴充之後, 也把擴充版本的 alt1, alt2 做出來\n",
    "            alt1 += \"0\" if i % 2 else \"1\"\n",
    "            alt2 += \"1\" if i % 2 else \"0\"\n",
    "            \n",
    "        result = float(\"inf\") # 要查的是最小值\n",
    "        # 最糟糕的狀況就是 s = 01010101, 要做 len(s) 長度次的 bit 翻轉\n",
    "        \n",
    "        diff1, diff2 = 0, 0\n",
    "        left = 0\n",
    "        \n",
    "        for right in range(len(s)):\n",
    "            if s[right] != alt1[right]: diff1 += 1\n",
    "            if s[right] != alt2[right]: diff2 += 1\n",
    "            \n",
    "            # 如果 sliding window 的長度已經比 s(還沒擴充前) 還要大\n",
    "            # 那就把左邊的元素踢掉, diff1, diff2 就要扣回去\n",
    "            if (right - left + 1) > n:\n",
    "                if s[left] != alt1[left]: diff1 -= 1\n",
    "                if s[left] != alt2[left]: diff2 -= 1\n",
    "                left += 1\n",
    "            \n",
    "            # 上面的 if 會進去的原因是 right += 1\n",
    "            # 最後 left += 1, 會讓 window 大小維持在 n\n",
    "            if (right - left + 1) == n:\n",
    "                result = min(result, diff1, diff2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + s\n",
    "        alt1,alt2 = '', ''\n",
    "        for i in range(len(s)):\n",
    "            alt1 += '0' if i % 2 == 0 else '1' \n",
    "            alt2 += '1' if i % 2 == 0 else '0' \n",
    "        \n",
    "        res = len(s)\n",
    "        diff1, diff2 = 0, 0\n",
    "\n",
    "        l = 0\n",
    "        for r in range(len(s)):\n",
    "            if s[r] != alt1[r]:\n",
    "                diff1 += 1\n",
    "            if s[r] != alt2[r]:\n",
    "                diff2 += 1\n",
    "            \n",
    "            if r - l + 1 > n:\n",
    "                if s[l] != alt1[l]:\n",
    "                    diff1 -= 1\n",
    "                if s[r] != alt2[l]:\n",
    "                    diff2 -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 == n:\n",
    "                res = min(res, diff1, diff2)\n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        has, a, jd = [0] * n, 0, 0\n",
    "        for i in range(n):\n",
    "            if int(s[i]) == jd: a += 1\n",
    "            jd, has[i] = 1 - jd, a\n",
    "        res, sm = min(a, n-a), has[-1]\n",
    "        if n % 2:\n",
    "            for i in range(n-1):\n",
    "                x = i + 1 + sm - 2 * has[i]\n",
    "                res = min(res, x, n - x)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0 for _ in range(n)]#store min flip from 0\n",
    "        choosing0 = True\n",
    "        for i in range(n):\n",
    "            if (choosing0 and s[i] != '0') or (not choosing0 and s[i] != '1'):\n",
    "                dp[i]+=1\n",
    "            if i > 0: \n",
    "                dp[i]+=dp[i-1]\n",
    "            choosing0 = not choosing0\n",
    "        def getMinByIJ(i, j):\n",
    "            return dp[j]-dp[i-1]\n",
    "        ret = dp[n-1]\n",
    "        for i in range(1, n):\n",
    "            rpn = n-i\n",
    "            lpn = i\n",
    "            rightStartZero = dp[n-1] - dp[i-1]\n",
    "            if i % 2 == 1:\n",
    "                rightStartZero = rpn - rightStartZero\n",
    "            if (n-i) % 2 == 1: \n",
    "                leftPart = i-dp[i-1]\n",
    "            else:\n",
    "                leftPart = dp[i-1]\n",
    "            curSum = leftPart + rightStartZero\n",
    "            curSum2 = n-curSum\n",
    "            # print(i, rightStartZero, leftPart)\n",
    "            # print(i, (n-i), curSum, curSum2)\n",
    "            curSum = min(curSum, curSum2)\n",
    "            ret = min(ret, curSum)\n",
    "        # print(dp)\n",
    "        if len(s) == 1: return 0\n",
    "        return ret\n",
    "\n",
    "\n",
    "            \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        n为偶数：\n",
    "        101010 或 010101  一定不用操作一\n",
    "\n",
    "        n为奇数：\n",
    "        10101 或 01010\n",
    "        11010、01101、10110、01011 或\n",
    "        00101、10010、01001、10100\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        # suffix0[i] 代表从末尾到i，i为0，不一样的数目\n",
    "        suffix0 = [0] * (n+1)\n",
    "        suffix1 = [0] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == \"0\":\n",
    "                suffix1[i] = suffix0[i+1] + 1\n",
    "                suffix0[i] = suffix1[i+1]\n",
    "            else:\n",
    "                suffix0[i] = suffix1[i+1] + 1\n",
    "                suffix1[i] = suffix0[i+1]\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            return min(suffix0[0], suffix1[0])\n",
    "        \n",
    "        # res0 代表从头到i，i为0，不一样的数目\n",
    "        ans = inf\n",
    "        res0, res1 = 0, 0\n",
    "        for i in range(n):\n",
    "            if s[i] == \"1\":\n",
    "                new_res0 = res1 + 1\n",
    "                new_res1 = res0\n",
    "            if s[i] == \"0\":\n",
    "                new_res0 = res1\n",
    "                new_res1 = res0 + 1\n",
    "            ans = min(ans, new_res0 + suffix0[i+1], new_res0 + suffix1[i+1], new_res1 + suffix0[i+1], new_res1 + suffix1[i+1])\n",
    "            res0 = new_res0\n",
    "            res1 = new_res1\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre01 = [0] * n\n",
    "        pre10 = [0] * n\n",
    "        for i,c in enumerate(s):\n",
    "            if c == '1':\n",
    "                if i % 2 == 0:\n",
    "                    pre01[i] = pre01[i-1] + 1\n",
    "                    pre10[i] = pre10[i-1]\n",
    "                else:\n",
    "                    pre10[i] += pre10[i-1] + 1\n",
    "                    pre01[i] = pre01[i-1]\n",
    "            else:\n",
    "                if i % 2 == 0:\n",
    "                    pre10[i] += pre10[i-1] + 1\n",
    "                    pre01[i] = pre01[i-1]\n",
    "                else:\n",
    "                    pre01[i] = pre01[i-1] + 1\n",
    "                    pre10[i] = pre10[i-1]\n",
    "        pre01 = [0] + pre01\n",
    "        pre10 = [0] + pre10\n",
    "        if n % 2 == 0:\n",
    "            return min(pre01[-1],pre10[-1])\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(n):\n",
    "            ans1 = pre01[-1] - pre01[i] + pre10[i]\n",
    "            ans2 = pre10[-1] - pre10[i] + pre01[i]\n",
    "            ans = min(ans, ans1, ans2)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        s += s\n",
    "        n = len(s)\n",
    "        s0, s1 = [], []\n",
    "        for i in range(n):\n",
    "            s0.append(i%2)\n",
    "            s1.append(i%2 ^ 1)\n",
    "        diff1 = diff2 = left = 0\n",
    "        ans = inf\n",
    "        for right in range(n):\n",
    "            if int(s[right]) != s0[right]:\n",
    "                diff1 += 1\n",
    "            if int(s[right]) != s1[right]:\n",
    "                diff2 += 1\n",
    "            if right - left + 1 == n//2:\n",
    "                ans = min(ans, diff1, diff2)\n",
    "                if int(s[left]) != s0[left]:\n",
    "                    diff1 -= 1\n",
    "                if int(s[left]) != s1[left]:\n",
    "                    diff2 -= 1\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        temp = len(s) * \"01\"\n",
    "        ss = 2 * s\n",
    "        arr = [0] * len(ss)\n",
    "        res = len(s)\n",
    "        for i in range(len(ss)):\n",
    "            if temp[i] != ss[i]:\n",
    "                arr[i] = 1\n",
    "            if i >= 1:\n",
    "                arr[i] += arr[i - 1]\n",
    "        for i in range(len(s), len(ss)):\n",
    "            res = min(res, arr[i] - arr[i - n], n - arr[i] + arr[i - n])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Double the string to consider all rotations\n",
    "        prefix = [0] * (2 * n + 1)\n",
    "        min_flips = float('inf')\n",
    "\n",
    "        # Calculate the prefix sum of flips needed for each position\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            prefix[i] = prefix[i - 1] + (i % 2 != int(s[i - 1]))\n",
    "\n",
    "        # Iterate through all possible starting positions\n",
    "        for start in range(n):\n",
    "            end = start + n\n",
    "            # Calculate flips needed for a string starting at 'start'\n",
    "            flips_needed = prefix[end] - prefix[start]\n",
    "            flips_needed = min(flips_needed, n - flips_needed)  # Consider the alternative flip\n",
    "            min_flips = min(min_flips, flips_needed)\n",
    "\n",
    "        return min_flips\n",
    "\n",
    "# Example usage:\n",
    "# solver = Solution()\n",
    "# s = \"001011\"\n",
    "# result = solver.minFlips(s)\n",
    "# print(result)  # Output will be the minimum number of flips needed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Double the string to consider all rotations\n",
    "        prefix = [0] * (2 * n + 1)\n",
    "        min_flips = float('inf')\n",
    "\n",
    "        # Calculate the prefix sum of flips needed for each position\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            prefix[i] = prefix[i - 1] + (i % 2 != int(s[i - 1]))\n",
    "\n",
    "        # Iterate through all possible starting positions\n",
    "        for start in range(n):\n",
    "            end = start + n\n",
    "            # Calculate flips needed for a string starting at 'start'\n",
    "            flips_needed = prefix[end] - prefix[start]\n",
    "            flips_needed = min(flips_needed, n - flips_needed)  # Consider the alternative flip\n",
    "            min_flips = min(min_flips, flips_needed)\n",
    "\n",
    "        return min_flips\n",
    "\n",
    "# Example usage:\n",
    "# solver = Solution()\n",
    "# s = \"001011\"\n",
    "# result = solver.minFlips(s)\n",
    "# print(result)  # Output will be the minimum number of flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Double the string to consider all rotations\n",
    "        prefix = [0] * (2 * n + 1)\n",
    "        min_flips = float('inf')\n",
    "\n",
    "        # Calculate the prefix sum of flips needed for each position\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            prefix[i] = prefix[i - 1] + (i % 2 != int(s[i - 1]))\n",
    "\n",
    "        # Iterate through all possible starting positions\n",
    "        for start in range(n):\n",
    "            end = start + n\n",
    "            # Calculate flips needed for a string starting at 'start'\n",
    "            flips_needed = prefix[end] - prefix[start]\n",
    "            flips_needed = min(flips_needed, n - flips_needed)  # Consider the alternative flip\n",
    "            min_flips = min(min_flips, flips_needed)\n",
    "\n",
    "        return min_flips\n",
    "\n",
    "# Example usage:\n",
    "# solver = Solution()\n",
    "# s = \"001011\"\n",
    "# result = solver.minFlips(s)\n",
    "# print(result)  # Output will be the minimum number of flips needed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        s = s * 2\n",
    "        tar = '01' * l\n",
    "        match = [0] * len(s)\n",
    "        for j in range(len(s)):\n",
    "            if (s[j] == tar[j]):\n",
    "                match[j] = 1\n",
    "        for j in range(1, len(s)):\n",
    "            match[j] += match[j-1]\n",
    "        \n",
    "        ans = l\n",
    "        for j in range(l, len(s)):\n",
    "            ans = min(ans, l-match[j]+match[j-l], match[j]-match[j-l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        s = s*2 \n",
    "        tgt = '01'*l # '10'*l和这个交替串没有任何交集，不需要创建\n",
    "\n",
    "        match = [0]*len(s)  \n",
    "        for j in range(len(s)):\n",
    "            if s[j]==tgt[j]: \n",
    "                match[j]=1\n",
    "\n",
    "        for j in range(1,len(s)): #原地求匹配情况数组的前缀和\n",
    "            match[j] += match[j-1]\n",
    "        \n",
    "        ans = l \n",
    "        for j in range(l,len(s)): \n",
    "            #从第二个合法位置开始计算可以避免特判边界，因为第一个合法位置和最后一个合法位置完全等价\n",
    "            mtch= match[j]-match[j-l]\n",
    "            ans = min(ans, l - mtch, mtch) \n",
    "            #同时处理两种交替串\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "\n",
    "        l = len(s)\n",
    "        s = s*2 \n",
    "        tgt = '01'*l # '10'*l和这个交替串没有任何交集，不需要创建\n",
    "\n",
    "        match = [0]*len(s)  \n",
    "        for j in range(len(s)):\n",
    "            if s[j]==tgt[j]: \n",
    "                match[j]=1\n",
    "\n",
    "        for j in range(1,len(s)): #原地求匹配情况数组的前缀和\n",
    "            match[j]+=match[j-1]\n",
    "        \n",
    "        ans = l \n",
    "        for j in range(l,len(s)): #从第二个合法位置开始计算可以避免特判边界，因为第一个合法位置和最后一个合法位置完全等价\n",
    "            ans = min(ans,l-match[j]+match[j-l],match[j]-match[j-l]) #同时处理两种交替串\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a, b = [0] * n, [0] * n\n",
    "        for i, ch in enumerate(s):\n",
    "            if i % 2 == 0:\n",
    "                if ch == '1':\n",
    "                    b[i] += 1\n",
    "                else:\n",
    "                    a[i] += 1\n",
    "            else:\n",
    "                if ch == '1':\n",
    "                    a[i] += 1\n",
    "                else:\n",
    "                    b[i] += 1\n",
    "\n",
    "        pa, pb = list(accumulate(a, initial=0)), list(accumulate(b, initial=0))\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            t = n - i\n",
    "            if i % 2 == 0:\n",
    "                x = pa[-1] - pa[i]\n",
    "                y = pb[-1] - pb[i]\n",
    "            else:\n",
    "                x = pb[-1] - pb[i]\n",
    "                y = pa[-1] - pa[i]\n",
    "                \n",
    "            if t % 2 == 0:\n",
    "                x += pa[i]\n",
    "                y += pb[i]\n",
    "            else:\n",
    "                x += pb[i]\n",
    "                y += pa[i]\n",
    "\n",
    "            ans = min(ans, x, y)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + s\n",
    "        p0_odd = [0] * (2 * n + 1)\n",
    "        p1_odd = [0] * (2 * n + 1)\n",
    "        p0_even = [0] * (2 * n + 1)\n",
    "        p1_even = [0] * (2 * n + 1)\n",
    "        for i in range(2*n):\n",
    "            p0_odd[i + 1] = p0_odd[i]\n",
    "            p1_odd[i + 1] = p1_odd[i]\n",
    "            p0_even[i + 1] = p0_even[i]\n",
    "            p1_even[i + 1] = p1_even[i]\n",
    "            if i & 1:\n",
    "                if s[i] == '1': p1_odd[i + 1] += 1\n",
    "                else: p0_odd[i + 1] += 1\n",
    "            else:\n",
    "                if s[i] == '1': p1_even[i + 1] += 1\n",
    "                else: p0_even[i + 1] += 1\n",
    "        res = inf\n",
    "        for i in range(n):\n",
    "            cmx = n + 1 >> 1\n",
    "            cmi = n - cmx\n",
    "            if i & 1:\n",
    "                # 101010\n",
    "                c1 = cmx - (p1_odd[i + n] - p1_odd[i])\n",
    "                c2 = cmi - (p0_even[i + n] - p0_even[i])\n",
    "                res = min(res, c1 + c2)\n",
    "                # 010101\n",
    "                c1 = cmx - (p0_odd[i + n] - p0_odd[i])\n",
    "                c2 = cmi - (p1_even[i + n] - p1_even[i])\n",
    "                res = min(res, c1 + c2)\n",
    "            else:\n",
    "                # 101010\n",
    "                c1 = cmx - (p1_even[i + n] - p1_even[i])\n",
    "                c2 = cmi - (p0_odd[i + n] - p0_odd[i])\n",
    "                res = min(res, c1 + c2)\n",
    "                # 010101\n",
    "                c1 = cmx - (p0_even[i + n] - p0_even[i])\n",
    "                c2 = cmi - (p1_odd[i + n] - p1_odd[i])\n",
    "                res = min(res, c1 + c2)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string with itself to handle circular cases\n",
    "        \n",
    "        # Count the flips needed for both \"0101...\" and \"1010...\" patterns\n",
    "        flips_0101 = [0] * (2 * n + 1)\n",
    "        flips_1010 = [0] * (2 * n + 1)\n",
    "        \n",
    "        for i in range(2 * n):\n",
    "            flips_0101[i + 1] = flips_0101[i] + (s[i] != '0' if i % 2 == 0 else s[i] != '1')\n",
    "            flips_1010[i + 1] = flips_1010[i] + (s[i] != '1' if i % 2 == 0 else s[i] != '0')\n",
    "        \n",
    "        min_flips = float('inf')\n",
    "        \n",
    "        for i in range(n):\n",
    "            # Calculate flips needed for pattern starting with '0' at index i\n",
    "            pattern_0101 = flips_0101[i + n] - flips_0101[i]\n",
    "            pattern_1010 = flips_1010[i + n] - flips_1010[i]\n",
    "            \n",
    "            min_flips = min(min_flips, pattern_0101, pattern_1010)\n",
    "        \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"0100101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output will be the minimum flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string to handle circular rotations\n",
    "        \n",
    "        # Initialize two arrays to store the number of flips required at even and odd positions\n",
    "        flips_even = [0] * (2 * n)\n",
    "        flips_odd = [0] * (2 * n)\n",
    "        \n",
    "        for i in range(2 * n):\n",
    "            flips_even[i] = int(s[i] != str(i % 2))\n",
    "            flips_odd[i] = int(s[i] != str((i + 1) % 2))\n",
    "            \n",
    "            if i > 0:\n",
    "                flips_even[i] += flips_even[i - 1]\n",
    "                flips_odd[i] += flips_odd[i - 1]\n",
    "                \n",
    "        min_flips = min(flips_even[n - 1], flips_odd[n - 1])\n",
    "        \n",
    "        for i in range(n, 2 * n - 1):\n",
    "            # Calculate flips required for substring of length n ending at index i\n",
    "            flips_required = min(\n",
    "                flips_even[i] - flips_even[i - n],\n",
    "                flips_odd[i] - flips_odd[i - n]\n",
    "            )\n",
    "            min_flips = min(min_flips, flips_required)\n",
    "            \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"010010\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output: 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string with itself to handle circular cases\n",
    "        \n",
    "        # Count the flips needed for both \"0101...\" and \"1010...\" patterns\n",
    "        flips_0101 = [0] * (2 * n + 1)\n",
    "        flips_1010 = [0] * (2 * n + 1)\n",
    "        \n",
    "        for i in range(2 * n):\n",
    "            flips_0101[i + 1] = flips_0101[i] + (s[i] != '0' if i % 2 == 0 else s[i] != '1')\n",
    "            flips_1010[i + 1] = flips_1010[i] + (s[i] != '1' if i % 2 == 0 else s[i] != '0')\n",
    "        \n",
    "        min_flips = float('inf')\n",
    "        \n",
    "        for i in range(n):\n",
    "            # Calculate flips needed for pattern starting with '0' at index i\n",
    "            pattern_0101 = flips_0101[i + n] - flips_0101[i]\n",
    "            pattern_1010 = flips_1010[i + n] - flips_1010[i]\n",
    "            \n",
    "            min_flips = min(min_flips, pattern_0101, pattern_1010)\n",
    "        \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"0100101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output will be the minimum flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string with itself to handle circular cases\n",
    "        \n",
    "        # Count the flips needed for both \"0101...\" and \"1010...\" patterns\n",
    "        flips_0101 = [0] * (2 * n + 1)\n",
    "        flips_1010 = [0] * (2 * n + 1)\n",
    "        \n",
    "        for i in range(2 * n):\n",
    "            flips_0101[i + 1] = flips_0101[i] + (s[i] != '0' if i % 2 == 0 else s[i] != '1')\n",
    "            flips_1010[i + 1] = flips_1010[i] + (s[i] != '1' if i % 2 == 0 else s[i] != '0')\n",
    "        \n",
    "        min_flips = float('inf')\n",
    "        \n",
    "        for i in range(n):\n",
    "            # Calculate flips needed for pattern starting with '0' at index i\n",
    "            pattern_0101 = flips_0101[i + n] - flips_0101[i]\n",
    "            pattern_1010 = flips_1010[i + n] - flips_1010[i]\n",
    "            \n",
    "            min_flips = min(min_flips, pattern_0101, pattern_1010)\n",
    "        \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"0100101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output will be the minimum flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string with itself to handle circular cases\n",
    "        \n",
    "        # Count the flips needed for both \"0101...\" and \"1010...\" patterns\n",
    "        flips_0101 = [0] * (2 * n + 1)\n",
    "        flips_1010 = [0] * (2 * n + 1)\n",
    "        \n",
    "        for i in range(2 * n):\n",
    "            flips_0101[i + 1] = flips_0101[i] + (s[i] != '0' if i % 2 == 0 else s[i] != '1')\n",
    "            flips_1010[i + 1] = flips_1010[i] + (s[i] != '1' if i % 2 == 0 else s[i] != '0')\n",
    "        \n",
    "        min_flips = float('inf')\n",
    "        \n",
    "        for i in range(n):\n",
    "            # Calculate flips needed for pattern starting with '0' at index i\n",
    "            pattern_0101 = flips_0101[i + n] - flips_0101[i]\n",
    "            pattern_1010 = flips_1010[i + n] - flips_1010[i]\n",
    "            \n",
    "            min_flips = min(min_flips, pattern_0101, pattern_1010)\n",
    "        \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"0100101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output will be the minimum flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s += s  # Concatenate the string with itself to handle circular cases\n",
    "        \n",
    "        # Count the flips needed for both \"0101...\" and \"1010...\" patterns\n",
    "        flips_0101 = [0] * (2 * n + 1)\n",
    "        flips_1010 = [0] * (2 * n + 1)\n",
    "        \n",
    "        for i in range(2 * n):\n",
    "            flips_0101[i + 1] = flips_0101[i] + (s[i] != '0' if i % 2 == 0 else s[i] != '1')\n",
    "            flips_1010[i + 1] = flips_1010[i] + (s[i] != '1' if i % 2 == 0 else s[i] != '0')\n",
    "        \n",
    "        min_flips = float('inf')\n",
    "        \n",
    "        for i in range(n):\n",
    "            # Calculate flips needed for pattern starting with '0' at index i\n",
    "            pattern_0101 = flips_0101[i + n] - flips_0101[i]\n",
    "            pattern_1010 = flips_1010[i + n] - flips_1010[i]\n",
    "            \n",
    "            min_flips = min(min_flips, pattern_0101, pattern_1010)\n",
    "        \n",
    "        return min_flips\n",
    "\n",
    "# Example usage\n",
    "solution = Solution()\n",
    "binary_string = \"0100101\"\n",
    "result = solution.minFlips(binary_string)\n",
    "print(result)  # Output will be the minimum flips needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        m = 2 * n\n",
    "        target0 = '01' * m\n",
    "        target1 = '10' * m\n",
    "        print(target0, target1)\n",
    "        s += s\n",
    "        cnt0 = [0] * m\n",
    "        cnt1 = [0] * m\n",
    "\n",
    "        for i, (x, y, z) in enumerate(zip(s, target0, target1)):\n",
    "            if x != y: cnt0[i] += 1\n",
    "            if x != z: cnt1[i] += 1\n",
    "        \n",
    "        pre_sum0 = list(accumulate(cnt0, initial = 0))\n",
    "        pre_sum1 = list(accumulate(cnt1, initial = 0))\n",
    "        #print(pre_sum0, pre_sum1)\n",
    "        ans = inf\n",
    "        for i in range(n, len(pre_sum0)):\n",
    "            ans = min(ans, pre_sum0[i] - pre_sum0[i - n], pre_sum1[i] - pre_sum1[i - n])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, s: str) -> int:\n",
    "        # 示性函数\n",
    "        I = lambda ch, x: int(ord(ch) - ord(\"0\") == x)\n",
    "        \n",
    "        n = len(s)\n",
    "        pre = [[0, 0] for _ in range(n)]\n",
    "        # 注意 i=0 的边界情况\n",
    "        for i in range(n):\n",
    "            pre[i][0] = (0 if i == 0 else pre[i - 1][1]) + I(s[i], 1)\n",
    "            pre[i][1] = (0 if i == 0 else pre[i - 1][0]) + I(s[i], 0)\n",
    "        \n",
    "        ans = min(pre[n - 1][0], pre[n - 1][1])\n",
    "        if n % 2 == 1:\n",
    "            # 如果 n 是奇数，还需要求出 suf\n",
    "            suf = [[0, 0] for _ in range(n)]\n",
    "            # 注意 i=n-1 的边界情况\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                suf[i][0] = (0 if i == n - 1 else suf[i + 1][1]) + I(s[i], 1)\n",
    "                suf[i][1] = (0 if i == n - 1 else suf[i + 1][0]) + I(s[i], 0)\n",
    "            \n",
    "            for i in range(n - 1):\n",
    "                ans = min(ans, pre[i][0] + suf[i + 1][0])\n",
    "                ans = min(ans, pre[i][1] + suf[i + 1][1])\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
